blob: e5b13b700d822041a42a99d59ccb8b8c95938f68 [file] [log] [blame]
Damien George04b91472014-05-03 23:27:38 +01001/*
Alexander Steffen55f33242017-06-30 09:22:17 +02002 * This file is part of the MicroPython project, http://micropython.org/
Damien George04b91472014-05-03 23:27:38 +01003 *
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
Damien429d7192013-10-04 19:53:11 +010027#include <assert.h>
28#include <string.h>
Damien Georgeea0461d2015-02-10 11:02:28 +000029#include <stdio.h>
Damien429d7192013-10-04 19:53:11 +010030
Damien Georgeb4b10fd2015-01-01 23:30:53 +000031#include "py/mpstate.h"
Damien George51dfcb42015-01-01 20:27:54 +000032#include "py/qstr.h"
33#include "py/gc.h"
Léa Saviotbc129f12019-11-22 10:07:08 +010034#include "py/runtime.h"
Damien429d7192013-10-04 19:53:11 +010035
Damien Georgeeb7bfcb2014-01-04 15:57:35 +000036// 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
Stefan Naumannace9fb52017-07-24 18:55:14 +020040#if MICROPY_DEBUG_VERBOSE // print debugging info
Paul Sokolovsky44739e22014-02-16 18:11:42 +020041#define DEBUG_printf DEBUG_printf
Damien Georgeeb7bfcb2014-01-04 15:57:35 +000042#else // don't print debugging info
Damien George1dc76af2014-02-26 16:57:08 +000043#define DEBUG_printf(...) (void)0
Damien Georgeeb7bfcb2014-01-04 15:57:35 +000044#endif
45
Damien George55baff42014-01-21 21:40:13 +000046// A qstr is an index into the qstr pool.
Damien Georgec3bd9412015-07-20 11:03:13 +000047// 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)
Damien George55baff42014-01-21 21:40:13 +000052
Damien Georgec3bd9412015-07-20 11:03:13 +000053#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)
Damien George95836f82015-01-11 22:27:30 +000066#if MICROPY_QSTR_BYTES_IN_LEN == 1
Damien Georgec3bd9412015-07-20 11:03:13 +000067 #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)
Damien George95836f82015-01-11 22:27:30 +000069#elif MICROPY_QSTR_BYTES_IN_LEN == 2
Damien Georgec3bd9412015-07-20 11:03:13 +000070 #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)
Damien George95836f82015-01-11 22:27:30 +000072#else
73 #error unimplemented qstr length decoding
74#endif
Damien George55baff42014-01-21 21:40:13 +000075
Damien Georgea1c93a62016-05-26 10:53:34 +000076#if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
Damien George1f54ad22016-05-26 09:06:46 +000077#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
Damien George0d165fe2018-12-13 17:08:26 +110084// 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
Damien George6e628c42014-03-25 15:27:15 +000088// this must match the equivalent function in makeqstrdata.py
Damien Georgec3f64d92015-11-27 12:23:18 +000089mp_uint_t qstr_compute_hash(const byte *data, size_t len) {
Damien George6e628c42014-03-25 15:27:15 +000090 // djb2 algorithm; see http://www.cse.yorku.ca/~oz/hash.html
Damien George40f3c022014-07-03 13:25:24 +010091 mp_uint_t hash = 5381;
Damien George55baff42014-01-21 21:40:13 +000092 for (const byte *top = data + len; data < top; data++) {
Damien George6e628c42014-03-25 15:27:15 +000093 hash = ((hash << 5) + hash) ^ (*data); // hash * 33 ^ data
Damien George55baff42014-01-21 21:40:13 +000094 }
Damien Georgec3bd9412015-07-20 11:03:13 +000095 hash &= Q_HASH_MASK;
Paul Sokolovsky59e269c2014-04-14 01:43:01 +030096 // Make sure that valid hash is never zero, zero means "hash not computed"
97 if (hash == 0) {
98 hash++;
99 }
100 return hash;
Damien George55baff42014-01-21 21:40:13 +0000101}
102
Damien George0a2e9652016-01-31 22:24:16 +0000103const qstr_pool_t mp_qstr_const_pool = {
Damien Georgeeb7bfcb2014-01-04 15:57:35 +0000104 NULL, // no previous pool
105 0, // no previous pool
Damien George0d165fe2018-12-13 17:08:26 +1100106 MICROPY_ALLOC_QSTR_ENTRIES_INIT,
Damien George0a2e9652016-01-31 22:24:16 +0000107 MP_QSTRnumber_of, // corresponds to number of strings in array just below
Damien Georgeeb7bfcb2014-01-04 15:57:35 +0000108 {
Damien George69661f32020-02-27 15:36:53 +1100109 #ifndef NO_QSTR
Damien George6942f802015-01-11 17:52:45 +0000110#define QDEF(id, str) str,
Damien George69661f32020-02-27 15:36:53 +1100111 #include "genhdr/qstrdefs.generated.h"
Damien George6942f802015-01-11 17:52:45 +0000112#undef QDEF
Damien George69661f32020-02-27 15:36:53 +1100113 #endif
Damien Georgeeb7bfcb2014-01-04 15:57:35 +0000114 },
115};
116
Damien George0a2e9652016-01-31 22:24:16 +0000117#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
Damien8b3a7c22013-10-23 20:20:17 +0100124void qstr_init(void) {
Damien George69661f32020-02-27 15:36:53 +1100125 MP_STATE_VM(last_pool) = (qstr_pool_t *)&CONST_POOL; // we won't modify the const_pool since it has no allocated room left
Damien Georgeade9a052015-06-13 21:53:22 +0100126 MP_STATE_VM(qstr_last_chunk) = NULL;
Damien George1f54ad22016-05-26 09:06:46 +0000127
David Lechneredbb73a2020-01-22 11:19:37 -0600128 #if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
Damien George1f54ad22016-05-26 09:06:46 +0000129 mp_thread_mutex_init(&MP_STATE_VM(qstr_mutex));
130 #endif
Damien429d7192013-10-04 19:53:11 +0100131}
132
Paul Sokolovsky520e2f52014-02-12 18:31:30 +0200133STATIC const byte *find_qstr(qstr q) {
Damien George55baff42014-01-21 21:40:13 +0000134 // search pool for this qstr
Damien George8e323b82017-11-29 16:58:27 +1100135 // 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;
Damien George55baff42014-01-21 21:40:13 +0000139 }
Damien George8e323b82017-11-29 16:58:27 +1100140 return pool->qstrs[q - pool->total_prev_len];
Damien George55baff42014-01-21 21:40:13 +0000141}
142
Damien George1f54ad22016-05-26 09:06:46 +0000143// qstr_mutex must be taken while in this function
Paul Sokolovsky520e2f52014-02-12 18:31:30 +0200144STATIC qstr qstr_add(const byte *q_ptr) {
Damien George55baff42014-01-21 21:40:13 +0000145 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));
Damien Georgeeb7bfcb2014-01-04 15:57:35 +0000146
147 // make sure we have room in the pool for a new qstr
Damien Georgeb4b10fd2015-01-01 23:30:53 +0000148 if (MP_STATE_VM(last_pool)->len >= MP_STATE_VM(last_pool)->alloc) {
Damien George0d165fe2018-12-13 17:08:26 +1100149 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
Damien George69661f32020-02-27 15:36:53 +1100154 qstr_pool_t *pool = m_new_obj_var_maybe(qstr_pool_t, const char *, new_alloc);
Damien George1f54ad22016-05-26 09:06:46 +0000155 if (pool == NULL) {
Emilie Feral58b56b92021-12-27 15:39:34 +0100156 // Keep qstr_last_chunk consistent with qstr_pool_t: qstr_last_chunk is not scanned
157 // at garbage collection since it's reachable from a qstr_pool_t. And the caller of
158 // this function expects q_ptr to be stored in a qstr_pool_t so it can be reached
159 // by the collector. If qstr_pool_t allocation failed, qstr_last_chunk needs to be
160 // NULL'd. Otherwise it may become a dangling pointer at the next garbage collection.
161 MP_STATE_VM(qstr_last_chunk) = NULL;
Damien George1f54ad22016-05-26 09:06:46 +0000162 QSTR_EXIT();
Damien George0d165fe2018-12-13 17:08:26 +1100163 m_malloc_fail(new_alloc);
Damien George1f54ad22016-05-26 09:06:46 +0000164 }
Damien Georgeb4b10fd2015-01-01 23:30:53 +0000165 pool->prev = MP_STATE_VM(last_pool);
166 pool->total_prev_len = MP_STATE_VM(last_pool)->total_prev_len + MP_STATE_VM(last_pool)->len;
Damien George0d165fe2018-12-13 17:08:26 +1100167 pool->alloc = new_alloc;
Damien Georgeeb7bfcb2014-01-04 15:57:35 +0000168 pool->len = 0;
Damien Georgeb4b10fd2015-01-01 23:30:53 +0000169 MP_STATE_VM(last_pool) = pool;
170 DEBUG_printf("QSTR: allocate new pool of size %d\n", MP_STATE_VM(last_pool)->alloc);
Damien429d7192013-10-04 19:53:11 +0100171 }
Damien Georgeeb7bfcb2014-01-04 15:57:35 +0000172
173 // add the new qstr
Damien Georgeb4b10fd2015-01-01 23:30:53 +0000174 MP_STATE_VM(last_pool)->qstrs[MP_STATE_VM(last_pool)->len++] = q_ptr;
Damien Georgeeb7bfcb2014-01-04 15:57:35 +0000175
176 // return id for the newly-added qstr
Damien Georgeb4b10fd2015-01-01 23:30:53 +0000177 return MP_STATE_VM(last_pool)->total_prev_len + MP_STATE_VM(last_pool)->len - 1;
Damien429d7192013-10-04 19:53:11 +0100178}
179
Damien Georgec3f64d92015-11-27 12:23:18 +0000180qstr qstr_find_strn(const char *str, size_t str_len) {
Damien George55baff42014-01-21 21:40:13 +0000181 // work out hash of str
Damien George69661f32020-02-27 15:36:53 +1100182 mp_uint_t str_hash = qstr_compute_hash((const byte *)str, str_len);
Damien George55baff42014-01-21 21:40:13 +0000183
184 // search pools for the data
Damien Georgeb4b10fd2015-01-01 23:30:53 +0000185 for (qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL; pool = pool->prev) {
Damien George55baff42014-01-21 21:40:13 +0000186 for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
Damien George1e708fe2014-01-23 18:27:51 +0000187 if (Q_GET_HASH(*q) == str_hash && Q_GET_LENGTH(*q) == str_len && memcmp(Q_GET_DATA(*q), str, str_len) == 0) {
Damien George55baff42014-01-21 21:40:13 +0000188 return pool->total_prev_len + (q - pool->qstrs);
Damien Georgeeb7bfcb2014-01-04 15:57:35 +0000189 }
Damien429d7192013-10-04 19:53:11 +0100190 }
191 }
Damien George55baff42014-01-21 21:40:13 +0000192
193 // not found; return null qstr
194 return 0;
Damien429d7192013-10-04 19:53:11 +0100195}
196
Damien George55baff42014-01-21 21:40:13 +0000197qstr qstr_from_str(const char *str) {
198 return qstr_from_strn(str, strlen(str));
Damien429d7192013-10-04 19:53:11 +0100199}
200
Damien Georgec3f64d92015-11-27 12:23:18 +0000201qstr qstr_from_strn(const char *str, size_t len) {
Damien George1f54ad22016-05-26 09:06:46 +0000202 QSTR_ENTER();
Damien George2617eeb2014-05-25 22:27:57 +0100203 qstr q = qstr_find_strn(str, len);
Damien George55baff42014-01-21 21:40:13 +0000204 if (q == 0) {
Damien Georgeade9a052015-06-13 21:53:22 +0100205 // qstr does not exist in interned pool so need to add it
206
Léa Saviotbc129f12019-11-22 10:07:08 +0100207 // check that len is not too big
208 if (len >= (1 << (8 * MICROPY_QSTR_BYTES_IN_LEN))) {
209 QSTR_EXIT();
Jim Mussareddef76fe2020-03-02 22:35:22 +1100210 mp_raise_msg(&mp_type_RuntimeError, MP_ERROR_TEXT("name too long"));
Léa Saviotbc129f12019-11-22 10:07:08 +0100211 }
212
Damien Georgeade9a052015-06-13 21:53:22 +0100213 // compute number of bytes needed to intern this string
Damien George25784852015-12-17 12:41:40 +0000214 size_t n_bytes = MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN + len + 1;
Damien Georgeade9a052015-06-13 21:53:22 +0100215
216 if (MP_STATE_VM(qstr_last_chunk) != NULL && MP_STATE_VM(qstr_last_used) + n_bytes > MP_STATE_VM(qstr_last_alloc)) {
217 // not enough room at end of previously interned string so try to grow
218 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);
219 if (new_p == NULL) {
220 // could not grow existing memory; shrink it to fit previous
Colin Hogbenf9b6b372016-10-31 14:05:56 +0000221 (void)m_renew_maybe(byte, MP_STATE_VM(qstr_last_chunk), MP_STATE_VM(qstr_last_alloc), MP_STATE_VM(qstr_last_used), false);
Damien Georgeade9a052015-06-13 21:53:22 +0100222 MP_STATE_VM(qstr_last_chunk) = NULL;
223 } else {
224 // could grow existing memory
225 MP_STATE_VM(qstr_last_alloc) += n_bytes;
226 }
227 }
228
229 if (MP_STATE_VM(qstr_last_chunk) == NULL) {
230 // no existing memory for the interned string so allocate a new chunk
Damien Georgec3f64d92015-11-27 12:23:18 +0000231 size_t al = n_bytes;
Damien Georgeade9a052015-06-13 21:53:22 +0100232 if (al < MICROPY_ALLOC_QSTR_CHUNK_INIT) {
233 al = MICROPY_ALLOC_QSTR_CHUNK_INIT;
234 }
235 MP_STATE_VM(qstr_last_chunk) = m_new_maybe(byte, al);
236 if (MP_STATE_VM(qstr_last_chunk) == NULL) {
237 // failed to allocate a large chunk so try with exact size
Damien George1f54ad22016-05-26 09:06:46 +0000238 MP_STATE_VM(qstr_last_chunk) = m_new_maybe(byte, n_bytes);
239 if (MP_STATE_VM(qstr_last_chunk) == NULL) {
240 QSTR_EXIT();
241 m_malloc_fail(n_bytes);
242 }
Damien Georgeade9a052015-06-13 21:53:22 +0100243 al = n_bytes;
244 }
245 MP_STATE_VM(qstr_last_alloc) = al;
246 MP_STATE_VM(qstr_last_used) = 0;
247 }
248
249 // allocate memory from the chunk for this new interned string's data
250 byte *q_ptr = MP_STATE_VM(qstr_last_chunk) + MP_STATE_VM(qstr_last_used);
251 MP_STATE_VM(qstr_last_used) += n_bytes;
252
253 // store the interned strings' data
Damien George69661f32020-02-27 15:36:53 +1100254 mp_uint_t hash = qstr_compute_hash((const byte *)str, len);
Damien Georgec3bd9412015-07-20 11:03:13 +0000255 Q_SET_HASH(q_ptr, hash);
Damien George95836f82015-01-11 22:27:30 +0000256 Q_SET_LENGTH(q_ptr, len);
Damien Georgec3bd9412015-07-20 11:03:13 +0000257 memcpy(q_ptr + MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN, str, len);
258 q_ptr[MICROPY_QSTR_BYTES_IN_HASH + MICROPY_QSTR_BYTES_IN_LEN + len] = '\0';
Damien George55baff42014-01-21 21:40:13 +0000259 q = qstr_add(q_ptr);
Damien429d7192013-10-04 19:53:11 +0100260 }
Damien George1f54ad22016-05-26 09:06:46 +0000261 QSTR_EXIT();
Damien George55baff42014-01-21 21:40:13 +0000262 return q;
Damien429d7192013-10-04 19:53:11 +0100263}
264
Damien George40f3c022014-07-03 13:25:24 +0100265mp_uint_t qstr_hash(qstr q) {
Damien George2b575412019-02-19 23:44:01 +1100266 const byte *qd = find_qstr(q);
267 return Q_GET_HASH(qd);
Damien George55baff42014-01-21 21:40:13 +0000268}
269
Damien Georgec3f64d92015-11-27 12:23:18 +0000270size_t qstr_len(qstr q) {
Damien George55baff42014-01-21 21:40:13 +0000271 const byte *qd = find_qstr(q);
272 return Q_GET_LENGTH(qd);
273}
274
Damien George55baff42014-01-21 21:40:13 +0000275const char *qstr_str(qstr q) {
276 const byte *qd = find_qstr(q);
Damien George69661f32020-02-27 15:36:53 +1100277 return (const char *)Q_GET_DATA(qd);
Damien George55baff42014-01-21 21:40:13 +0000278}
279
Damien Georgec3f64d92015-11-27 12:23:18 +0000280const byte *qstr_data(qstr q, size_t *len) {
Damien George55baff42014-01-21 21:40:13 +0000281 const byte *qd = find_qstr(q);
282 *len = Q_GET_LENGTH(qd);
283 return Q_GET_DATA(qd);
Damien429d7192013-10-04 19:53:11 +0100284}
Damien George4d5b28c2014-01-29 18:56:46 +0000285
Damien George25784852015-12-17 12:41:40 +0000286void qstr_pool_info(size_t *n_pool, size_t *n_qstr, size_t *n_str_data_bytes, size_t *n_total_bytes) {
Damien George1f54ad22016-05-26 09:06:46 +0000287 QSTR_ENTER();
Damien George4d5b28c2014-01-29 18:56:46 +0000288 *n_pool = 0;
289 *n_qstr = 0;
290 *n_str_data_bytes = 0;
291 *n_total_bytes = 0;
Damien George0a2e9652016-01-31 22:24:16 +0000292 for (qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL && pool != &CONST_POOL; pool = pool->prev) {
Damien George4d5b28c2014-01-29 18:56:46 +0000293 *n_pool += 1;
294 *n_qstr += pool->len;
295 for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
296 *n_str_data_bytes += Q_GET_ALLOC(*q);
297 }
Damien George0b13f3e2014-10-24 23:12:25 +0100298 #if MICROPY_ENABLE_GC
299 *n_total_bytes += gc_nbytes(pool); // this counts actual bytes used in heap
300 #else
Damien George4d5b28c2014-01-29 18:56:46 +0000301 *n_total_bytes += sizeof(qstr_pool_t) + sizeof(qstr) * pool->alloc;
Damien George0b13f3e2014-10-24 23:12:25 +0100302 #endif
Damien George4d5b28c2014-01-29 18:56:46 +0000303 }
304 *n_total_bytes += *n_str_data_bytes;
Damien George1f54ad22016-05-26 09:06:46 +0000305 QSTR_EXIT();
Damien George4d5b28c2014-01-29 18:56:46 +0000306}
Damien Georgeea0461d2015-02-10 11:02:28 +0000307
308#if MICROPY_PY_MICROPYTHON_MEM_INFO
309void qstr_dump_data(void) {
Damien George1f54ad22016-05-26 09:06:46 +0000310 QSTR_ENTER();
Damien George0a2e9652016-01-31 22:24:16 +0000311 for (qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL && pool != &CONST_POOL; pool = pool->prev) {
Damien Georgeea0461d2015-02-10 11:02:28 +0000312 for (const byte **q = pool->qstrs, **q_top = pool->qstrs + pool->len; q < q_top; q++) {
Damien Georgee72cda92015-04-11 12:15:47 +0100313 mp_printf(&mp_plat_print, "Q(%s)\n", Q_GET_DATA(*q));
Damien Georgeea0461d2015-02-10 11:02:28 +0000314 }
315 }
Damien George1f54ad22016-05-26 09:06:46 +0000316 QSTR_EXIT();
Damien Georgeea0461d2015-02-10 11:02:28 +0000317}
318#endif
Jim Mussared154b4eb2019-09-26 22:19:29 +1000319
320#if MICROPY_ROM_TEXT_COMPRESSION
321
322#ifdef NO_QSTR
323
324// If NO_QSTR is set, it means we're doing QSTR extraction.
325// So we won't yet have "genhdr/compressed.data.h"
326
327#else
328
329// Emit the compressed_string_data string.
330#define MP_COMPRESSED_DATA(x) STATIC const char *compressed_string_data = x;
331#define MP_MATCH_COMPRESSED(a, b)
332#include "genhdr/compressed.data.h"
333#undef MP_COMPRESSED_DATA
334#undef MP_MATCH_COMPRESSED
335
336#endif // NO_QSTR
337
338// This implements the "common word" compression scheme (see makecompresseddata.py) where the most
339// common 128 words in error messages are replaced by their index into the list of common words.
340
341// The compressed string data is delimited by setting high bit in the final char of each word.
342// e.g. aaaa<0x80|a>bbbbbb<0x80|b>....
343// This method finds the n'th string.
344STATIC const byte *find_uncompressed_string(uint8_t n) {
345 const byte *c = (byte *)compressed_string_data;
346 while (n > 0) {
347 while ((*c & 0x80) == 0) {
348 ++c;
349 }
350 ++c;
351 --n;
352 }
353 return c;
354}
355
356// Given a compressed string in src, decompresses it into dst.
357// dst must be large enough (use MP_MAX_UNCOMPRESSED_TEXT_LEN+1).
358void mp_decompress_rom_string(byte *dst, const mp_rom_error_text_t src_chr) {
359 // Skip past the 0xff marker.
360 const byte *src = (byte *)src_chr + 1;
361 // Need to add spaces around compressed words, except for the first (i.e. transition from 1<->2).
362 // 0 = start, 1 = compressed, 2 = regular.
363 int state = 0;
364 while (*src) {
365 if ((byte) * src >= 128) {
366 if (state != 0) {
367 *dst++ = ' ';
368 }
369 state = 1;
370
371 // High bit set, replace with common word.
372 const byte *word = find_uncompressed_string(*src & 0x7f);
373 // The word is terminated by the final char having its high bit set.
374 while ((*word & 0x80) == 0) {
375 *dst++ = *word++;
376 }
377 *dst++ = (*word & 0x7f);
378 } else {
379 // Otherwise just copy one char.
380 if (state == 1) {
381 *dst++ = ' ';
382 }
383 state = 2;
384
385 *dst++ = *src;
386 }
387 ++src;
388 }
389 // Add null-terminator.
390 *dst = 0;
391}
392
393#endif // MICROPY_ROM_TEXT_COMPRESSION