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