Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/zint/backend/reedsol.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /* This is a simple Reed-Solomon encoder */
2 /*
3 (C) Cliff Hones 2004
4
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
7 are met:
8
9 1. Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
11 2. Redistributions in binary form must reproduce the above copyright
12 notice, this list of conditions and the following disclaimer in the
13 documentation and/or other materials provided with the distribution.
14 3. Neither the name of the project nor the names of its contributors
15 may be used to endorse or promote products derived from this software
16 without specific prior written permission.
17
18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
19 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
22 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 SUCH DAMAGE.
29 */
30 /* SPDX-License-Identifier: BSD-3-Clause */
31
32 /* It is not written with high efficiency in mind, so is probably
33 // not suitable for real-time encoding. The aim was to keep it
34 // simple, general and clear.
35 //
36 // <Some notes on the theory and implementation need to be added here>
37
38 // Usage:
39 // First call rs_init_gf(&rs, prime_poly) to set up the Galois Field parameters.
40 // Then call rs_init_code(&rs, nsym, index) to set the encoding size
41 // Then call rs_encode(&rs, datalen, data, out) to encode the data.
42 //
43 // These can be called repeatedly as required - but note that
44 // rs_init_code must be called following any rs_init_gf call.
45 //
46 // If the parameters are fixed, some of the statics below can be
47 // replaced with constants in the obvious way, and additionally
48 // malloc/free can be avoided by using static arrays of a suitable
49 // size.
50 // Note: use of statics has been done for (up to) 8-bit tables.
51 */
52
53 #include "common.h"
54 #include "reedsol.h"
55 #include "reedsol_logs.h"
56
57 /* rs_init_gf(&rs, prime_poly) initialises the parameters for the Galois Field.
58 // The symbol size is determined from the highest bit set in poly
59 // This implementation will support sizes up to 8 bits (see rs_uint_init_gf()
60 // for sizes > 8 bits and <= 30 bits) - bit sizes of 8 or 4 are typical
61 //
62 // The poly is the bit pattern representing the GF characteristic
63 // polynomial. e.g. for ECC200 (8-bit symbols) the polynomial is
64 // a**8 + a**5 + a**3 + a**2 + 1, which translates to 0x12d.
65 */
66
67 INTERNAL void rs_init_gf(rs_t *rs, const unsigned int prime_poly) {
68 struct item {
69 const unsigned char *logt;
70 const unsigned char *alog;
71 };
72 /* To add a new prime poly of degree <= 8 add its details to this table and to the table in `test_generate()`
73 in "backend/tests/test_reedsol.c" and regenerate the log tables by running
74 "backend/tests/test_reedsol -f generate -g". Paste the result in "reedsol_logs.h" */
75 static const struct item data[] = {
76 { logt_0x13, alog_0x13 }, /* 0 000- */
77 { logt_0x25, alog_0x25 }, /* 0 001- */
78 { logt_0x43, alog_0x43 }, /* 0 010- */
79 { NULL, NULL },
80 { logt_0x89, alog_0x89 }, /* 0 100- */
81 { NULL, NULL },
82 { NULL, NULL },
83 { NULL, NULL },
84 { logt_0x11d, alog_0x11d }, /* 1 000- */
85 { logt_0x12d, alog_0x12d }, /* 1 001- */
86 { NULL, NULL },
87 { logt_0x163, alog_0x163 }, /* 1 011- */
88 };
89
90 /* Using bits 9-6 as hash to save a few cycles */
91 /* Alter this hash or just iterate if new prime poly added that doesn't fit */
92 const unsigned int hash = prime_poly >> 5;
93
94 rs->logt = data[hash].logt;
95 rs->alog = data[hash].alog;
96 }
97
98 /* rs_init_code(&rs, nsym, index) initialises the Reed-Solomon encoder
99 // nsym is the number of symbols to be generated (to be appended
100 // to the input data). index is usually 1 - it is the index of
101 // the constant in the first term (i) of the RS generator polynomial:
102 // (x + 2**i)*(x + 2**(i+1))*... [nsym terms]
103 // For ECC200, index is 1.
104 */
105
106 INTERNAL void rs_init_code(rs_t *rs, const int nsym, int index) {
107 int i, k;
108 const unsigned char *const logt = rs->logt;
109 const unsigned char *const alog = rs->alog;
110 unsigned char *rspoly = rs->rspoly;
111 unsigned char *log_rspoly = rs->log_rspoly;
112
113 rs->nsym = nsym;
114
115 rspoly[0] = 1;
116 for (i = 1; i <= nsym; i++) {
117 rspoly[i] = 1;
118 for (k = i - 1; k > 0; k--) {
119 if (rspoly[k])
120 rspoly[k] = alog[logt[rspoly[k]] + index]; /* Multiply coeff by 2**index */
121 rspoly[k] ^= rspoly[k - 1]; /* Add coeff of x**(k-1) * x */
122 }
123 rspoly[0] = alog[logt[rspoly[0]] + index]; /* 2**(i + (i+1) + ... + index) */
124 index++;
125 }
126
127 /* Set logs of poly and check if have zero coeffs */
128 rs->zero = 0;
129 for (i = 0; i <= nsym; i++) {
130 log_rspoly[i] = logt[rspoly[i]]; /* For simplicity allow log of 0 */
131 rs->zero |= rspoly[i] == 0;
132 }
133 }
134
135 /* rs_encode(&rs, datalen, data, res) generates nsym Reed-Solomon codes (nsym as given in rs_init_code()) */
136 INTERNAL void rs_encode(const rs_t *rs, const int datalen, const unsigned char *data, unsigned char *res) {
137 int i, k;
138 const unsigned char *const logt = rs->logt;
139 const unsigned char *const alog = rs->alog;
140 const unsigned char *const rspoly = rs->rspoly;
141 const unsigned char *const log_rspoly = rs->log_rspoly;
142 const int nsym = rs->nsym;
143 const int nsym_halved = nsym >> 1;
144
145 memset(res, 0, nsym);
146 if (rs->zero) { /* Poly has a zero coeff so need to check in inner loop */
147 for (i = 0; i < datalen; i++) {
148 const unsigned int m = res[nsym - 1] ^ data[i];
149 if (m) {
150 const unsigned int log_m = logt[m];
151 for (k = nsym - 1; k > 0; k--) {
152 if (rspoly[k])
153 res[k] = (unsigned char) (res[k - 1] ^ alog[log_m + log_rspoly[k]]);
154 else
155 res[k] = res[k - 1];
156 }
157 res[0] = alog[log_m + log_rspoly[0]];
158 } else {
159 memmove(res + 1, res, nsym - 1);
160 res[0] = 0;
161 }
162 }
163 } else { /* Avoid a branch in inner loop */
164 for (i = 0; i < datalen; i++) {
165 const unsigned int m = res[nsym - 1] ^ data[i];
166 if (m) {
167 const unsigned int log_m = logt[m];
168 for (k = nsym - 1; k > 0; k--) {
169 res[k] = (unsigned char) (res[k - 1] ^ alog[log_m + log_rspoly[k]]);
170 }
171 res[0] = alog[log_m + log_rspoly[0]];
172 } else {
173 memmove(res + 1, res, nsym - 1);
174 res[0] = 0;
175 }
176 }
177 }
178 /* Reverse the result */
179 for (i = 0; i < nsym_halved; i++) {
180 const unsigned char tmp = res[i];
181 res[i] = res[nsym - 1 - i];
182 res[nsym - 1 - i] = tmp;
183 }
184 }
185
186 /* The same as above but for unsigned int data and result - Aztec code compatible */
187
188 INTERNAL void rs_encode_uint(const rs_t *rs, const int datalen, const unsigned int *data, unsigned int *res) {
189 int i, k;
190 const unsigned char *const logt = rs->logt;
191 const unsigned char *const alog = rs->alog;
192 const unsigned char *const rspoly = rs->rspoly;
193 const unsigned char *const log_rspoly = rs->log_rspoly;
194 const int nsym = rs->nsym;
195 const int nsym_halved = nsym >> 1;
196
197 memset(res, 0, sizeof(unsigned int) * nsym);
198 if (rs->zero) { /* Poly has a zero coeff so need to check in inner loop */
199 for (i = 0; i < datalen; i++) {
200 const unsigned int m = res[nsym - 1] ^ data[i];
201 if (m) {
202 const unsigned int log_m = logt[m];
203 for (k = nsym - 1; k > 0; k--) {
204 if (rspoly[k])
205 res[k] = res[k - 1] ^ alog[log_m + log_rspoly[k]];
206 else
207 res[k] = res[k - 1];
208 }
209 res[0] = alog[log_m + log_rspoly[0]];
210 } else {
211 memmove(res + 1, res, sizeof(unsigned int) * (nsym - 1));
212 res[0] = 0;
213 }
214 }
215 } else { /* Avoid a branch in inner loop */
216 for (i = 0; i < datalen; i++) {
217 const unsigned int m = res[nsym - 1] ^ data[i];
218 if (m) {
219 const unsigned int log_m = logt[m];
220 for (k = nsym - 1; k > 0; k--) {
221 res[k] = res[k - 1] ^ alog[log_m + log_rspoly[k]];
222 }
223 res[0] = alog[log_m + log_rspoly[0]];
224 } else {
225 memmove(res + 1, res, sizeof(unsigned int) * (nsym - 1));
226 res[0] = 0;
227 }
228 }
229 }
230 /* Reverse the result */
231 for (i = 0; i < nsym_halved; i++) {
232 const unsigned int tmp = res[i];
233 res[i] = res[nsym - 1 - i];
234 res[nsym - 1 - i] = tmp;
235 }
236 }
237
238 /* Versions of the above for bitlengths > 8 and <= 30 and unsigned int data and results - Aztec code compatible */
239
240 /* Usage:
241 // First call rs_uint_init_gf(&rs_uint, prime_poly, logmod) to set up the Galois Field parameters.
242 // Then call rs_uint_init_code(&rs_uint, nsym, index) to set the encoding size
243 // Then call rs_uint_encode(&rs_uint, datalen, data, out) to encode the data.
244 // Then call rs_uint_free(&rs_uint) to free the log tables.
245 */
246
247 /* `logmod` (field characteristic) will be 2**bitlength - 1, eg 1023 for bitlength 10, 4095 for bitlength 12 */
248 INTERNAL int rs_uint_init_gf(rs_uint_t *rs_uint, const unsigned int prime_poly, const int logmod) {
249 int b, p, v;
250 unsigned int *logt, *alog;
251
252 b = logmod + 1;
253
254 rs_uint->logt = NULL;
255 rs_uint->alog = NULL;
256
257 if (!(logt = (unsigned int *) calloc(b, sizeof(unsigned int)))) {
258 return 0;
259 }
260 if (!(alog = (unsigned int *) calloc(b * 2, sizeof(unsigned int)))) {
261 free(logt);
262 return 0;
263 }
264
265 /* Calculate the log/alog tables */
266 for (p = 1, v = 0; v < logmod; v++) {
267 alog[v] = p;
268 alog[logmod + v] = p; /* Double up, avoids mod */
269 logt[p] = v;
270 p <<= 1;
271 if (p & b) /* If overflow */
272 p ^= prime_poly; /* Subtract prime poly */
273 }
274 rs_uint->logt = logt;
275 rs_uint->alog = alog;
276 return 1;
277 }
278
279 INTERNAL void rs_uint_init_code(rs_uint_t *rs_uint, const int nsym, int index) {
280 int i, k;
281 const unsigned int *const logt = rs_uint->logt;
282 const unsigned int *const alog = rs_uint->alog;
283 unsigned short *rspoly = rs_uint->rspoly;
284 unsigned int *log_rspoly = rs_uint->log_rspoly;
285
286 if (logt == NULL || alog == NULL) {
287 return;
288 }
289 rs_uint->nsym = nsym;
290
291 rspoly[0] = 1;
292 for (i = 1; i <= nsym; i++) {
293 rspoly[i] = 1;
294 for (k = i - 1; k > 0; k--) {
295 if (rspoly[k])
296 rspoly[k] = alog[(logt[rspoly[k]] + index)];
297 rspoly[k] ^= rspoly[k - 1];
298 }
299 rspoly[0] = alog[(logt[rspoly[0]] + index)];
300 index++;
301 }
302
303 /* Set logs of poly and check if have zero coeffs */
304 rs_uint->zero = 0;
305 for (i = 0; i <= nsym; i++) {
306 log_rspoly[i] = logt[rspoly[i]]; /* For simplicity allow log of 0 */
307 rs_uint->zero |= rspoly[i] == 0;
308 }
309 }
310
311 INTERNAL void rs_uint_encode(const rs_uint_t *rs_uint, const int datalen, const unsigned int *data,
312 unsigned int *res) {
313 int i, k;
314 const unsigned int *const logt = rs_uint->logt;
315 const unsigned int *const alog = rs_uint->alog;
316 const unsigned short *const rspoly = rs_uint->rspoly;
317 const unsigned int *const log_rspoly = rs_uint->log_rspoly;
318 const int nsym = rs_uint->nsym;
319 const int nsym_halved = nsym >> 1;
320
321 memset(res, 0, sizeof(unsigned int) * nsym);
322 if (logt == NULL || alog == NULL) {
323 return;
324 }
325 if (rs_uint->zero) { /* Poly has a zero coeff so need to check in inner loop */
326 for (i = 0; i < datalen; i++) {
327 const unsigned int m = res[nsym - 1] ^ data[i];
328 if (m) {
329 const unsigned int log_m = logt[m];
330 for (k = nsym - 1; k > 0; k--) {
331 if (rspoly[k])
332 res[k] = res[k - 1] ^ alog[log_m + log_rspoly[k]];
333 else
334 res[k] = res[k - 1];
335 }
336 res[0] = alog[log_m + log_rspoly[0]];
337 } else {
338 memmove(res + 1, res, sizeof(unsigned int) * (nsym - 1));
339 res[0] = 0;
340 }
341 }
342 } else { /* Avoid a branch in inner loop */
343 for (i = 0; i < datalen; i++) {
344 const unsigned int m = res[nsym - 1] ^ data[i];
345 if (m) {
346 const unsigned int log_m = logt[m];
347 for (k = nsym - 1; k > 0; k--) {
348 res[k] = res[k - 1] ^ alog[log_m + log_rspoly[k]];
349 }
350 res[0] = alog[log_m + log_rspoly[0]];
351 } else {
352 memmove(res + 1, res, sizeof(unsigned int) * (nsym - 1));
353 res[0] = 0;
354 }
355 }
356 }
357 /* Reverse the result */
358 for (i = 0; i < nsym_halved; i++) {
359 const unsigned int tmp = res[i];
360 res[i] = res[nsym - 1 - i];
361 res[nsym - 1 - i] = tmp;
362 }
363 }
364
365 INTERNAL void rs_uint_free(rs_uint_t *rs_uint) {
366 if (rs_uint->logt) {
367 free(rs_uint->logt);
368 rs_uint->logt = NULL;
369 }
370 if (rs_uint->alog) {
371 free(rs_uint->alog);
372 rs_uint->alog = NULL;
373 }
374 }
375
376 /* vim: set ts=4 sw=4 et : */