1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424
|
/*
* This file is part of the MicroPython project, http://micropython.org/
*
* The MIT License (MIT)
*
* Copyright (c) 2013, 2014 Damien P. George
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
*/
#ifndef MICROPY_INCLUDED_PY_MISC_H
#define MICROPY_INCLUDED_PY_MISC_H
// a mini library of useful types and functions
/** types *******************************************************/
#include <stdbool.h>
#include <stdint.h>
#include <stddef.h>
typedef unsigned char byte;
typedef unsigned int uint;
/** generic ops *************************************************/
#ifndef MIN
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#endif
#ifndef MAX
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#endif
// Classical double-indirection stringification of preprocessor macro's value
#define MP_STRINGIFY_HELPER(x) #x
#define MP_STRINGIFY(x) MP_STRINGIFY_HELPER(x)
// Static assertion macro
#define MP_STATIC_ASSERT(cond) ((void)sizeof(char[1 - 2 * !(cond)]))
// In C++ things like comparing extern const pointers are not constant-expressions so cannot be used
// in MP_STATIC_ASSERT. Note that not all possible compiler versions will reject this. Some gcc versions
// do, others only with -Werror=vla, msvc always does.
// The (void) is needed to avoid "left operand of comma operator has no effect [-Werror=unused-value]"
// when using this macro on the left-hand side of a comma.
#if defined(_MSC_VER) || defined(__cplusplus)
#define MP_STATIC_ASSERT_NONCONSTEXPR(cond) ((void)1)
#else
#define MP_STATIC_ASSERT_NONCONSTEXPR(cond) MP_STATIC_ASSERT(cond)
#endif
// Round-up integer division
#define MP_CEIL_DIVIDE(a, b) (((a) + (b) - 1) / (b))
#define MP_ROUND_DIVIDE(a, b) (((a) + (b) / 2) / (b))
/** memory allocation ******************************************/
// TODO make a lazy m_renew that can increase by a smaller amount than requested (but by at least 1 more element)
#define m_new(type, num) ((type *)(m_malloc(sizeof(type) * (num))))
#define m_new_maybe(type, num) ((type *)(m_malloc_maybe(sizeof(type) * (num))))
#define m_new0(type, num) ((type *)(m_malloc0(sizeof(type) * (num))))
#define m_new_obj(type) (m_new(type, 1))
#define m_new_obj_maybe(type) (m_new_maybe(type, 1))
#define m_new_obj_var(obj_type, var_field, var_type, var_num) ((obj_type *)m_malloc(offsetof(obj_type, var_field) + sizeof(var_type) * (var_num)))
#define m_new_obj_var0(obj_type, var_field, var_type, var_num) ((obj_type *)m_malloc0(offsetof(obj_type, var_field) + sizeof(var_type) * (var_num)))
#define m_new_obj_var_maybe(obj_type, var_field, var_type, var_num) ((obj_type *)m_malloc_maybe(offsetof(obj_type, var_field) + sizeof(var_type) * (var_num)))
#if MICROPY_MALLOC_USES_ALLOCATED_SIZE
#define m_renew(type, ptr, old_num, new_num) ((type *)(m_realloc((ptr), sizeof(type) * (old_num), sizeof(type) * (new_num))))
#define m_renew_maybe(type, ptr, old_num, new_num, allow_move) ((type *)(m_realloc_maybe((ptr), sizeof(type) * (old_num), sizeof(type) * (new_num), (allow_move))))
#define m_del(type, ptr, num) m_free(ptr, sizeof(type) * (num))
#define m_del_var(obj_type, var_field, var_type, var_num, ptr) (m_free(ptr, offsetof(obj_type, var_field) + sizeof(var_type) * (var_num)))
#else
#define m_renew(type, ptr, old_num, new_num) ((type *)(m_realloc((ptr), sizeof(type) * (new_num))))
#define m_renew_maybe(type, ptr, old_num, new_num, allow_move) ((type *)(m_realloc_maybe((ptr), sizeof(type) * (new_num), (allow_move))))
#define m_del(type, ptr, num) ((void)(num), m_free(ptr))
#define m_del_var(obj_type, var_field, var_type, var_num, ptr) ((void)(var_num), m_free(ptr))
#endif
#define m_del_obj(type, ptr) (m_del(type, ptr, 1))
void *m_malloc(size_t num_bytes);
void *m_malloc_maybe(size_t num_bytes);
void *m_malloc_with_finaliser(size_t num_bytes);
void *m_malloc0(size_t num_bytes);
#if MICROPY_MALLOC_USES_ALLOCATED_SIZE
void *m_realloc(void *ptr, size_t old_num_bytes, size_t new_num_bytes);
void *m_realloc_maybe(void *ptr, size_t old_num_bytes, size_t new_num_bytes, bool allow_move);
void m_free(void *ptr, size_t num_bytes);
#else
void *m_realloc(void *ptr, size_t new_num_bytes);
void *m_realloc_maybe(void *ptr, size_t new_num_bytes, bool allow_move);
void m_free(void *ptr);
#endif
NORETURN void m_malloc_fail(size_t num_bytes);
#if MICROPY_TRACKED_ALLOC
// These alloc/free functions track the pointers in a linked list so the GC does not reclaim
// them. They can be used by code that requires traditional C malloc/free semantics.
void *m_tracked_calloc(size_t nmemb, size_t size);
void m_tracked_free(void *ptr_in);
#endif
#if MICROPY_MEM_STATS
size_t m_get_total_bytes_allocated(void);
size_t m_get_current_bytes_allocated(void);
size_t m_get_peak_bytes_allocated(void);
#endif
/** array helpers ***********************************************/
// get the number of elements in a fixed-size array
#define MP_ARRAY_SIZE(a) (sizeof(a) / sizeof((a)[0]))
// align ptr to the nearest multiple of "alignment"
#define MP_ALIGN(ptr, alignment) (void *)(((uintptr_t)(ptr) + ((alignment) - 1)) & ~((alignment) - 1))
/** unichar / UTF-8 *********************************************/
#if MICROPY_PY_BUILTINS_STR_UNICODE
// with unicode enabled we need a type which can fit chars up to 0x10ffff
typedef uint32_t unichar;
#else
// without unicode enabled we can only need to fit chars up to 0xff
// (on 16-bit archs uint is 16-bits and more efficient than uint32_t)
typedef uint unichar;
#endif
#if MICROPY_PY_BUILTINS_STR_UNICODE
unichar utf8_get_char(const byte *s);
const byte *utf8_next_char(const byte *s);
size_t utf8_charlen(const byte *str, size_t len);
#else
static inline unichar utf8_get_char(const byte *s) {
return *s;
}
static inline const byte *utf8_next_char(const byte *s) {
return s + 1;
}
static inline size_t utf8_charlen(const byte *str, size_t len) {
(void)str;
return len;
}
#endif
bool unichar_isspace(unichar c);
bool unichar_isalpha(unichar c);
bool unichar_isprint(unichar c);
bool unichar_isdigit(unichar c);
bool unichar_isxdigit(unichar c);
bool unichar_isident(unichar c);
bool unichar_isalnum(unichar c);
bool unichar_isupper(unichar c);
bool unichar_islower(unichar c);
unichar unichar_tolower(unichar c);
unichar unichar_toupper(unichar c);
mp_uint_t unichar_xdigit_value(unichar c);
#define UTF8_IS_NONASCII(ch) ((ch) & 0x80)
#define UTF8_IS_CONT(ch) (((ch) & 0xC0) == 0x80)
/** variable string *********************************************/
typedef struct _vstr_t {
size_t alloc;
size_t len;
char *buf;
bool fixed_buf;
} vstr_t;
// convenience macro to declare a vstr with a fixed size buffer on the stack
#define VSTR_FIXED(vstr, alloc) vstr_t vstr; char vstr##_buf[(alloc)]; vstr_init_fixed_buf(&vstr, (alloc), vstr##_buf);
void vstr_init(vstr_t *vstr, size_t alloc);
void vstr_init_len(vstr_t *vstr, size_t len);
void vstr_init_fixed_buf(vstr_t *vstr, size_t alloc, char *buf);
struct _mp_print_t;
void vstr_init_print(vstr_t *vstr, size_t alloc, struct _mp_print_t *print);
void vstr_clear(vstr_t *vstr);
vstr_t *vstr_new(size_t alloc);
void vstr_free(vstr_t *vstr);
static inline void vstr_reset(vstr_t *vstr) {
vstr->len = 0;
}
static inline char *vstr_str(vstr_t *vstr) {
return vstr->buf;
}
static inline size_t vstr_len(vstr_t *vstr) {
return vstr->len;
}
void vstr_hint_size(vstr_t *vstr, size_t size);
char *vstr_extend(vstr_t *vstr, size_t size);
char *vstr_add_len(vstr_t *vstr, size_t len);
char *vstr_null_terminated_str(vstr_t *vstr);
void vstr_add_byte(vstr_t *vstr, byte v);
void vstr_add_char(vstr_t *vstr, unichar chr);
void vstr_add_str(vstr_t *vstr, const char *str);
void vstr_add_strn(vstr_t *vstr, const char *str, size_t len);
void vstr_ins_byte(vstr_t *vstr, size_t byte_pos, byte b);
void vstr_ins_char(vstr_t *vstr, size_t char_pos, unichar chr);
void vstr_cut_head_bytes(vstr_t *vstr, size_t bytes_to_cut);
void vstr_cut_tail_bytes(vstr_t *vstr, size_t bytes_to_cut);
void vstr_cut_out_bytes(vstr_t *vstr, size_t byte_pos, size_t bytes_to_cut);
void vstr_printf(vstr_t *vstr, const char *fmt, ...);
/** non-dynamic size-bounded variable buffer/string *************/
#define CHECKBUF(buf, max_size) char buf[max_size + 1]; size_t buf##_len = max_size; char *buf##_p = buf;
#define CHECKBUF_RESET(buf, max_size) buf##_len = max_size; buf##_p = buf;
#define CHECKBUF_APPEND(buf, src, src_len) \
{ size_t l = MIN(src_len, buf##_len); \
memcpy(buf##_p, src, l); \
buf##_len -= l; \
buf##_p += l; }
#define CHECKBUF_APPEND_0(buf) { *buf##_p = 0; }
#define CHECKBUF_LEN(buf) (buf##_p - buf)
#ifdef va_start
void vstr_vprintf(vstr_t *vstr, const char *fmt, va_list ap);
#endif
// Debugging helpers
int DEBUG_printf(const char *fmt, ...);
extern mp_uint_t mp_verbose_flag;
/** float internals *************/
#if MICROPY_PY_BUILTINS_FLOAT
#if MICROPY_FLOAT_IMPL == MICROPY_FLOAT_IMPL_DOUBLE
#define MP_FLOAT_EXP_BITS (11)
#define MP_FLOAT_EXP_OFFSET (1023)
#define MP_FLOAT_FRAC_BITS (52)
typedef uint64_t mp_float_uint_t;
#elif MICROPY_FLOAT_IMPL == MICROPY_FLOAT_IMPL_FLOAT
#define MP_FLOAT_EXP_BITS (8)
#define MP_FLOAT_EXP_OFFSET (127)
#define MP_FLOAT_FRAC_BITS (23)
typedef uint32_t mp_float_uint_t;
#endif
#define MP_FLOAT_EXP_BIAS ((1 << (MP_FLOAT_EXP_BITS - 1)) - 1)
typedef union _mp_float_union_t {
mp_float_t f;
#if MP_ENDIANNESS_LITTLE
struct {
mp_float_uint_t frc : MP_FLOAT_FRAC_BITS;
mp_float_uint_t exp : MP_FLOAT_EXP_BITS;
mp_float_uint_t sgn : 1;
} p;
#else
struct {
mp_float_uint_t sgn : 1;
mp_float_uint_t exp : MP_FLOAT_EXP_BITS;
mp_float_uint_t frc : MP_FLOAT_FRAC_BITS;
} p;
#endif
mp_float_uint_t i;
} mp_float_union_t;
#endif // MICROPY_PY_BUILTINS_FLOAT
/** ROM string compression *************/
#if MICROPY_ROM_TEXT_COMPRESSION
#if MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_NONE
#error "MICROPY_ERROR_REPORTING_NONE requires MICROPY_ROM_TEXT_COMPRESSION disabled"
#endif
#ifdef NO_QSTR
// Compression enabled but doing QSTR extraction.
// So leave MP_COMPRESSED_ROM_TEXT in place for makeqstrdefs.py / makecompresseddata.py to find them.
#else
// Compression enabled and doing a regular build.
// Map MP_COMPRESSED_ROM_TEXT to the compressed strings.
// Force usage of the MP_ERROR_TEXT macro by requiring an opaque type.
typedef struct {
#if defined(__clang__) || defined(_MSC_VER)
// Fix "error: empty struct has size 0 in C, size 1 in C++", and the msvc counterpart
// "C requires that a struct or union have at least one member"
char dummy;
#endif
} *mp_rom_error_text_t;
#include <string.h>
inline MP_ALWAYSINLINE const char *MP_COMPRESSED_ROM_TEXT(const char *msg) {
// "genhdr/compressed.data.h" contains an invocation of the MP_MATCH_COMPRESSED macro for each compressed string.
// The giant if(strcmp) tree is optimized by the compiler, which turns this into a direct return of the compressed data.
#define MP_MATCH_COMPRESSED(a, b) if (strcmp(msg, a) == 0) { return b; } else
// It also contains a single invocation of the MP_COMPRESSED_DATA macro, we don't need that here.
#define MP_COMPRESSED_DATA(x)
#include "genhdr/compressed.data.h"
#undef MP_COMPRESSED_DATA
#undef MP_MATCH_COMPRESSED
return msg;
}
#endif
#else
// Compression not enabled, just make it a no-op.
typedef const char *mp_rom_error_text_t;
#define MP_COMPRESSED_ROM_TEXT(x) x
#endif // MICROPY_ROM_TEXT_COMPRESSION
// Might add more types of compressed text in the future.
// For now, forward directly to MP_COMPRESSED_ROM_TEXT.
#define MP_ERROR_TEXT(x) (mp_rom_error_text_t)MP_COMPRESSED_ROM_TEXT(x)
// Portable implementations of CLZ and CTZ intrinsics
#ifdef _MSC_VER
#include <intrin.h>
static inline uint32_t mp_clz(uint32_t x) {
unsigned long lz = 0;
return _BitScanReverse(&lz, x) ? (sizeof(x) * 8 - 1) - lz : 0;
}
static inline uint32_t mp_clzl(unsigned long x) {
unsigned long lz = 0;
return _BitScanReverse(&lz, x) ? (sizeof(x) * 8 - 1) - lz : 0;
}
#ifdef _WIN64
static inline uint32_t mp_clzll(unsigned long long x) {
unsigned long lz = 0;
return _BitScanReverse64(&lz, x) ? (sizeof(x) * 8 - 1) - lz : 0;
}
#else
// Microsoft don't ship _BitScanReverse64 on Win32, so emulate it
static inline uint32_t mp_clzll(unsigned long long x) {
unsigned long h = x >> 32;
return h ? mp_clzl(h) : (mp_clzl((unsigned long)x) + 32);
}
#endif
static inline uint32_t mp_ctz(uint32_t x) {
unsigned long tz = 0;
return _BitScanForward(&tz, x) ? tz : 0;
}
// Workaround for 'warning C4127: conditional expression is constant'.
static inline bool mp_check(bool value) {
return value;
}
static inline uint32_t mp_popcount(uint32_t x) {
return __popcnt(x);
}
#else
#define mp_clz(x) __builtin_clz(x)
#define mp_clzl(x) __builtin_clzl(x)
#define mp_clzll(x) __builtin_clzll(x)
#define mp_ctz(x) __builtin_ctz(x)
#define mp_check(x) (x)
#if defined __has_builtin
#if __has_builtin(__builtin_popcount)
#define mp_popcount(x) __builtin_popcount(x)
#endif
#endif
#if !defined(mp_popcount)
static inline uint32_t mp_popcount(uint32_t x) {
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
return x * 0x01010101;
}
#endif
#endif
// mp_int_t can be larger than long, i.e. Windows 64-bit, nan-box variants
static inline uint32_t mp_clz_mpi(mp_int_t x) {
#ifdef __XC16__
mp_uint_t mask = MP_OBJ_WORD_MSBIT_HIGH;
mp_uint_t zeroes = 0;
while (mask != 0) {
if (mask & (mp_uint_t)x) {
break;
}
zeroes++;
mask >>= 1;
}
return zeroes;
#else
MP_STATIC_ASSERT(sizeof(mp_int_t) == sizeof(long long)
|| sizeof(mp_int_t) == sizeof(long));
// ugly, but should compile to single intrinsic unless O0 is set
if (mp_check(sizeof(mp_int_t) == sizeof(long))) {
return mp_clzl((unsigned long)x);
} else {
return mp_clzll((unsigned long long)x);
}
#endif
}
#endif // MICROPY_INCLUDED_PY_MISC_H
|