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
27#include <assert.h>
28#include <string.h>
29#include <stdio.h>
30
31#include "py/mpstate.h"
32#include "py/qstr.h"
33#include "py/gc.h"
34#include "py/runtime.h"
35
36// NOTE: we are using linear arrays to store and search for qstr's (unique strings, interned strings)
37// ultimately we will replace this with a static hash table of some kind
38// also probably need to include the length in the string data, to allow null bytes in the string
39
40#if MICROPY_DEBUG_VERBOSE // print debugging info
41#define DEBUG_printf DEBUG_printf
42#else // don't print debugging info
43#define DEBUG_printf(...) (void)0
44#endif
45
46// A qstr is an index into the qstr pool.
47// The data for a qstr contains (hash, length, data):
48// - hash (configurable number of bytes)
49// - length (configurable number of bytes)
50// - data ("length" number of bytes)
51// - \0 terminated (so they can be printed using printf)
52
53#if MICROPY_QSTR_BYTES_IN_HASH == 1
54 #define Q_HASH_MASK (0xff)
55 #define Q_GET_HASH(q) ((mp_uint_t)(q)[0])
56 #define Q_SET_HASH(q, hash) do { (q)[0] = (hash); } while (0)
57#elif MICROPY_QSTR_BYTES_IN_HASH == 2
58 #define Q_HASH_MASK (0xffff)
59 #define Q_GET_HASH(q) ((mp_uint_t)(q)[0] | ((mp_uint_t)(q)[1] << 8))
60 #define Q_SET_HASH(q, hash) do { (q)[0] = (hash); (q)[1] = (hash) >> 8; } while (0)
61#else
62 #error unimplemented qstr hash decoding
63#endif
64#define Q_GET_ALLOC(q) (MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN + Q_GET_LENGTH(q) + 1)
65#define Q_GET_DATA(q) ((q) + MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN)
66#if MICROPY_QSTR_BYTES_IN_LEN == 1
67 #define Q_GET_LENGTH(q) ((q)[MICROPY_QSTR_BYTES_IN_HASH])
68 #define Q_SET_LENGTH(q, len) do { (q)[MICROPY_QSTR_BYTES_IN_HASH] = (len); } while (0)
69#elif MICROPY_QSTR_BYTES_IN_LEN == 2
70 #define Q_GET_LENGTH(q) ((q)[MICROPY_QSTR_BYTES_IN_HASH] | ((q)[MICROPY_QSTR_BYTES_IN_HASH + 1] << 8))
71 #define Q_SET_LENGTH(q, len) do { (q)[MICROPY_QSTR_BYTES_IN_HASH] = (len); (q)[MICROPY_QSTR_BYTES_IN_HASH + 1] = (len) >> 8; } while (0)
72#else
73 #error unimplemented qstr length decoding
74#endif
75
76#if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
77#define QSTR_ENTER() mp_thread_mutex_lock(&MP_STATE_VM(qstr_mutex), 1)
78#define QSTR_EXIT() mp_thread_mutex_unlock(&MP_STATE_VM(qstr_mutex))
79#else
80#define QSTR_ENTER()
81#define QSTR_EXIT()
82#endif
83
84// Initial number of entries for qstr pool, set so that the first dynamically
85// allocated pool is twice this size. The value here must be <= MP_QSTRnumber_of.
86#define MICROPY_ALLOC_QSTR_ENTRIES_INIT (10)
87
88// this must match the equivalent function in makeqstrdata.py
89mp_uint_t qstr_compute_hash(const byte *data, size_t len) {
90 // djb2 algorithm; see http://www.cse.yorku.ca/~oz/hash.html
91 mp_uint_t hash = 5381;
92 for (const byte *top = data + len; data < top; data++) {
93 hash = ((hash << 5) + hash) ^ (*data); // hash * 33 ^ data
94 }
95 hash &= Q_HASH_MASK;
96 // Make sure that valid hash is never zero, zero means "hash not computed"
97 if (hash == 0) {
98 hash++;
99 }
100 return hash;
101}
102
103const qstr_pool_t mp_qstr_const_pool = {
104 NULL, // no previous pool
105 0, // no previous pool
106 MICROPY_ALLOC_QSTR_ENTRIES_INIT,
107 MP_QSTRnumber_of, // corresponds to number of strings in array just below
108 {
109 #ifndef NO_QSTR
110#define QDEF(id, str) str,
111 #include "genhdr/qstrdefs.generated.h"
112#undef QDEF
113 #endif
114 },
115};
116
117#ifdef MICROPY_QSTR_EXTRA_POOL
118extern const qstr_pool_t MICROPY_QSTR_EXTRA_POOL;
119#define CONST_POOL MICROPY_QSTR_EXTRA_POOL
120#else
121#define CONST_POOL mp_qstr_const_pool
122#endif
123
124void qstr_init(void) {
125 MP_STATE_VM(last_pool) = (qstr_pool_t *)&CONST_POOL; // we won't modify the const_pool since it has no allocated room left
126 MP_STATE_VM(qstr_last_chunk) = NULL;
127
128 #if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
129 mp_thread_mutex_init(&MP_STATE_VM(qstr_mutex));
130 #endif
131}
132
133STATIC const byte *find_qstr(qstr q) {
134 // search pool for this qstr
135 // total_prev_len==0 in the final pool, so the loop will always terminate
136 qstr_pool_t *pool = MP_STATE_VM(last_pool);
137 while (q < pool->total_prev_len) {
138 pool = pool->prev;
139 }
140 return pool->qstrs[q - pool->total_prev_len];
141}
142
143// qstr_mutex must be taken while in this function
144STATIC qstr qstr_add(const byte *q_ptr) {
145 DEBUG_printf("QSTR: add hash=%d len=%d data=%.*s\n", Q_GET_HASH(q_ptr), Q_GET_LENGTH(q_ptr), Q_GET_LENGTH(q_ptr), Q_GET_DATA(q_ptr));
146
147 // make sure we have room in the pool for a new qstr
148 if (MP_STATE_VM(last_pool)->len >= MP_STATE_VM(last_pool)->alloc) {
149 size_t new_alloc = MP_STATE_VM(last_pool)->alloc * 2;
150 #ifdef MICROPY_QSTR_EXTRA_POOL
151 // Put a lower bound on the allocation size in case the extra qstr pool has few entries
152 new_alloc = MAX(MICROPY_ALLOC_QSTR_ENTRIES_INIT, new_alloc);
153 #endif
154 qstr_pool_t *pool = m_new_obj_var_maybe(qstr_pool_t, const char *, new_alloc);
155 if (pool == NULL) {
156 QSTR_EXIT();
157 m_malloc_fail(new_alloc);
158 }
159 pool->prev = MP_STATE_VM(last_pool);
160 pool->total_prev_len = MP_STATE_VM(last_pool)->total_prev_len + MP_STATE_VM(last_pool)->len;
161 pool->alloc = new_alloc;
162 pool->len = 0;
163 MP_STATE_VM(last_pool) = pool;
164 DEBUG_printf("QSTR: allocate new pool of size %d\n", MP_STATE_VM(last_pool)->alloc);
165 }
166
167 // add the new qstr
168 MP_STATE_VM(last_pool)->qstrs[MP_STATE_VM(last_pool)->len++] = q_ptr;
169
170 // return id for the newly-added qstr
171 return MP_STATE_VM(last_pool)->total_prev_len + MP_STATE_VM(last_pool)->len - 1;
172}
173
174qstr qstr_find_strn(const char *str, size_t str_len) {
175 // work out hash of str
176 mp_uint_t str_hash = qstr_compute_hash((const byte *)str, str_len);
177
178 // search pools for the data
179 for (qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL; pool = pool->prev) {
180 for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
181 if (Q_GET_HASH(*q) == str_hash && Q_GET_LENGTH(*q) == str_len && memcmp(Q_GET_DATA(*q), str, str_len) == 0) {
182 return pool->total_prev_len + (q - pool->qstrs);
183 }
184 }
185 }
186
187 // not found; return null qstr
188 return 0;
189}
190
191qstr qstr_from_str(const char *str) {
192 return qstr_from_strn(str, strlen(str));
193}
194
195qstr qstr_from_strn(const char *str, size_t len) {
196 QSTR_ENTER();
197 qstr q = qstr_find_strn(str, len);
198 if (q == 0) {
199 // qstr does not exist in interned pool so need to add it
200
201 // check that len is not too big
202 if (len >= (1 << (8 * MICROPY_QSTR_BYTES_IN_LEN))) {
203 QSTR_EXIT();
204 mp_raise_msg(&mp_type_RuntimeError, MP_ERROR_TEXT("name too long"));
205 }
206
207 // compute number of bytes needed to intern this string
208 size_t n_bytes = MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN + len + 1;
209
210 if (MP_STATE_VM(qstr_last_chunk) != NULL && MP_STATE_VM(qstr_last_used) + n_bytes > MP_STATE_VM(qstr_last_alloc)) {
211 // not enough room at end of previously interned string so try to grow
212 byte *new_p = m_renew_maybe(byte, MP_STATE_VM(qstr_last_chunk), MP_STATE_VM(qstr_last_alloc), MP_STATE_VM(qstr_last_alloc) + n_bytes, false);
213 if (new_p == NULL) {
214 // could not grow existing memory; shrink it to fit previous
215 (void)m_renew_maybe(byte, MP_STATE_VM(qstr_last_chunk), MP_STATE_VM(qstr_last_alloc), MP_STATE_VM(qstr_last_used), false);
216 MP_STATE_VM(qstr_last_chunk) = NULL;
217 } else {
218 // could grow existing memory
219 MP_STATE_VM(qstr_last_alloc) += n_bytes;
220 }
221 }
222
223 if (MP_STATE_VM(qstr_last_chunk) == NULL) {
224 // no existing memory for the interned string so allocate a new chunk
225 size_t al = n_bytes;
226 if (al < MICROPY_ALLOC_QSTR_CHUNK_INIT) {
227 al = MICROPY_ALLOC_QSTR_CHUNK_INIT;
228 }
229 MP_STATE_VM(qstr_last_chunk) = m_new_maybe(byte, al);
230 if (MP_STATE_VM(qstr_last_chunk) == NULL) {
231 // failed to allocate a large chunk so try with exact size
232 MP_STATE_VM(qstr_last_chunk) = m_new_maybe(byte, n_bytes);
233 if (MP_STATE_VM(qstr_last_chunk) == NULL) {
234 QSTR_EXIT();
235 m_malloc_fail(n_bytes);
236 }
237 al = n_bytes;
238 }
239 MP_STATE_VM(qstr_last_alloc) = al;
240 MP_STATE_VM(qstr_last_used) = 0;
241 }
242
243 // allocate memory from the chunk for this new interned string's data
244 byte *q_ptr = MP_STATE_VM(qstr_last_chunk) + MP_STATE_VM(qstr_last_used);
245 MP_STATE_VM(qstr_last_used) += n_bytes;
246
247 // store the interned strings' data
248 mp_uint_t hash = qstr_compute_hash((const byte *)str, len);
249 Q_SET_HASH(q_ptr, hash);
250 Q_SET_LENGTH(q_ptr, len);
251 memcpy(q_ptr + MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN, str, len);
252 q_ptr[MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN + len] = '\0';
253 q = qstr_add(q_ptr);
254 }
255 QSTR_EXIT();
256 return q;
257}
258
259mp_uint_t qstr_hash(qstr q) {
260 const byte *qd = find_qstr(q);
261 return Q_GET_HASH(qd);
262}
263
264size_t qstr_len(qstr q) {
265 const byte *qd = find_qstr(q);
266 return Q_GET_LENGTH(qd);
267}
268
269const char *qstr_str(qstr q) {
270 const byte *qd = find_qstr(q);
271 return (const char *)Q_GET_DATA(qd);
272}
273
274const byte *qstr_data(qstr q, size_t *len) {
275 const byte *qd = find_qstr(q);
276 *len = Q_GET_LENGTH(qd);
277 return Q_GET_DATA(qd);
278}
279
280void qstr_pool_info(size_t *n_pool, size_t *n_qstr, size_t *n_str_data_bytes, size_t *n_total_bytes) {
281 QSTR_ENTER();
282 *n_pool = 0;
283 *n_qstr = 0;
284 *n_str_data_bytes = 0;
285 *n_total_bytes = 0;
286 for (qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL && pool != &CONST_POOL; pool = pool->prev) {
287 *n_pool += 1;
288 *n_qstr += pool->len;
289 for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
290 *n_str_data_bytes += Q_GET_ALLOC(*q);
291 }
292 #if MICROPY_ENABLE_GC
293 *n_total_bytes += gc_nbytes(pool); // this counts actual bytes used in heap
294 #else
295 *n_total_bytes += sizeof(qstr_pool_t) + sizeof(qstr) * pool->alloc;
296 #endif
297 }
298 *n_total_bytes += *n_str_data_bytes;
299 QSTR_EXIT();
300}
301
302#if MICROPY_PY_MICROPYTHON_MEM_INFO
303void qstr_dump_data(void) {
304 QSTR_ENTER();
305 for (qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL && pool != &CONST_POOL; pool = pool->prev) {
306 for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
307 mp_printf(&mp_plat_print, "Q(%s)\n", Q_GET_DATA(*q));
308 }
309 }
310 QSTR_EXIT();
311}
312#endif
313
314#if MICROPY_ROM_TEXT_COMPRESSION
315
316#ifdef NO_QSTR
317
318// If NO_QSTR is set, it means we're doing QSTR extraction.
319// So we won't yet have "genhdr/compressed.data.h"
320
321#else
322
323// Emit the compressed_string_data string.
324#define MP_COMPRESSED_DATA(x) STATIC const char *compressed_string_data = x;
325#define MP_MATCH_COMPRESSED(a, b)
326#include "genhdr/compressed.data.h"
327#undef MP_COMPRESSED_DATA
328#undef MP_MATCH_COMPRESSED
329
330#endif // NO_QSTR
331
332// This implements the "common word" compression scheme (see makecompresseddata.py) where the most
333// common 128 words in error messages are replaced by their index into the list of common words.
334
335// The compressed string data is delimited by setting high bit in the final char of each word.
336// e.g. aaaa<0x80|a>bbbbbb<0x80|b>....
337// This method finds the n'th string.
338STATIC const byte *find_uncompressed_string(uint8_t n) {
339 const byte *c = (byte *)compressed_string_data;
340 while (n > 0) {
341 while ((*c & 0x80) == 0) {
342 ++c;
343 }
344 ++c;
345 --n;
346 }
347 return c;
348}
349
350// Given a compressed string in src, decompresses it into dst.
351// dst must be large enough (use MP_MAX_UNCOMPRESSED_TEXT_LEN+1).
352void mp_decompress_rom_string(byte *dst, const mp_rom_error_text_t src_chr) {
353 // Skip past the 0xff marker.
354 const byte *src = (byte *)src_chr + 1;
355 // Need to add spaces around compressed words, except for the first (i.e. transition from 1<->2).
356 // 0 = start, 1 = compressed, 2 = regular.
357 int state = 0;
358 while (*src) {
359 if ((byte) * src >= 128) {
360 if (state != 0) {
361 *dst++ = ' ';
362 }
363 state = 1;
364
365 // High bit set, replace with common word.
366 const byte *word = find_uncompressed_string(*src & 0x7f);
367 // The word is terminated by the final char having its high bit set.
368 while ((*word & 0x80) == 0) {
369 *dst++ = *word++;
370 }
371 *dst++ = (*word & 0x7f);
372 } else {
373 // Otherwise just copy one char.
374 if (state == 1) {
375 *dst++ = ' ';
376 }
377 state = 2;
378
379 *dst++ = *src;
380 }
381 ++src;
382 }
383 // Add null-terminator.
384 *dst = 0;
385}
386
387#endif // MICROPY_ROM_TEXT_COMPRESSION
388