Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/zint/backend/large.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 /* large.c - Handles binary manipulation of large numbers */
2 /*
3 libzint - the open source barcode library
4 Copyright (C) 2008-2023 Robin Stuart <rstuart114@gmail.com>
5
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions
8 are met:
9
10 1. Redistributions of source code must retain the above copyright
11 notice, this list of conditions and the following disclaimer.
12 2. Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in the
14 documentation and/or other materials provided with the distribution.
15 3. Neither the name of the project nor the names of its contributors
16 may be used to endorse or promote products derived from this software
17 without specific prior written permission.
18
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
20 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 SUCH DAMAGE.
30 */
31 /* SPDX-License-Identifier: BSD-3-Clause */
32
33 /* `large_mul_u64()` and `large_div_u64()` are adapted from articles by F. W. Jacob
34 * https://www.codeproject.com/Tips/618570/UInt-Multiplication-Squaring
35 * "This article, along with any associated source code and files, is licensed under The BSD License"
36 * http://www.codeproject.com/Tips/785014/UInt-Division-Modulus
37 * "This article, along with any associated source code and files, is licensed under The BSD License"
38 *
39 * These in turn are based on Hacker's Delight (2nd Edition, 2012) by Henry S. Warren, Jr.
40 * "You are free to use, copy, and distribute any of the code on this web site, whether modified by you or not."
41 * https://web.archive.org/web/20190716204559/http://www.hackersdelight.org/permissions.htm
42 *
43 * `clz_u64()` and other bits and pieces are adapted from r128.h by Alan Hickman (fahickman)
44 * https://github.com/fahickman/r128/blob/master/r128.h
45 * "R128 is released into the public domain. See LICENSE for details." LICENSE is The Unlicense.
46 */
47 #include <assert.h>
48 #include <stdio.h>
49 #include "common.h"
50 #include "large.h"
51
52 #define MASK32 0xFFFFFFFF
53
54 /* Convert decimal string `s` of (at most) length `length` to 64-bit and place in 128-bit `t` */
55 INTERNAL void large_load_str_u64(large_uint *t, const unsigned char *s, const int length) {
56 uint64_t val = 0;
57 const unsigned char *const se = s + length;
58 for (; s < se && z_isdigit(*s); s++) {
59 val *= 10;
60 val += *s - '0';
61 }
62 t->lo = val;
63 t->hi = 0;
64 }
65
66 /* Add 128-bit `s` to 128-bit `t` */
67 INTERNAL void large_add(large_uint *t, const large_uint *s) {
68 t->lo += s->lo;
69 t->hi += s->hi + (t->lo < s->lo);
70 }
71
72 /* Add 64-bit `s` to 128-bit `t` */
73 INTERNAL void large_add_u64(large_uint *t, const uint64_t s) {
74 t->lo += s;
75 if (t->lo < s) {
76 t->hi++;
77 }
78 }
79
80 /* Subtract 64-bit `s` from 128-bit `t` */
81 INTERNAL void large_sub_u64(large_uint *t, const uint64_t s) {
82 uint64_t r = t->lo - s;
83 if (r > t->lo) {
84 t->hi--;
85 }
86 t->lo = r;
87 }
88
89 /* Multiply 128-bit `t` by 64-bit `s`
90 * See Jacob `mult64to128()` and Warren Section 8-2
91 * Note '0' denotes low 32-bits, '1' high 32-bits
92 * if p00 == s0 * tlo0
93 * k00 == carry of p00
94 * p01 == s0 * tlo1
95 * k01 == carry of (p01 + k00)
96 * p10 == s1 * tlo0
97 * k10 == carry of p10
98 * p11 == s1 * tlo1 (unmasked, i.e. including unshifted carry if any)
99 * then t->lo == (p01 + p10 + k00) << 32 + p00
100 * and t->hi == p11 + k10 + k01 + thi * s
101 *
102 * (thi) tlo1 tlo0
103 * x s1 s0
104 * -------------------------
105 * p00
106 * k01 p01 + k00
107 * p10
108 * p11 + k10
109 */
110 INTERNAL void large_mul_u64(large_uint *t, const uint64_t s) {
111 uint64_t thi = t->hi;
112 uint64_t tlo0 = t->lo & MASK32;
113 uint64_t tlo1 = t->lo >> 32;
114
115 uint64_t s0 = s & MASK32;
116 uint64_t s1 = s >> 32;
117
118 uint64_t tmp = s0 * tlo0; /* p00 (unmasked) */
119 uint64_t p00 = tmp & MASK32;
120 uint64_t k10;
121
122 tmp = (s1 * tlo0) + (tmp >> 32); /* (p10 + k00) (p10 unmasked) */
123 k10 = tmp >> 32;
124
125 tmp = (s0 * tlo1) + (tmp & MASK32); /* (p01 + p10 + k00) (p01 unmasked) */
126
127 t->lo = (tmp << 32) + p00; /* (p01 + p10 + k00) << 32 + p00 (note any carry from unmasked p01 shifted out) */
128 t->hi = (s1 * tlo1) + k10 + (tmp >> 32) + thi * s; /* p11 + k10 + k01 + thi * s */
129 }
130
131 /* Count leading zeroes. See Hickman `r128__clz64()` */
132 static int clz_u64(uint64_t x) {
133 uint64_t n = 64, y;
134 y = x >> 32; if (y) { n -= 32; x = y; }
135 y = x >> 16; if (y) { n -= 16; x = y; }
136 y = x >> 8; if (y) { n -= 8; x = y; }
137 y = x >> 4; if (y) { n -= 4; x = y; }
138 y = x >> 2; if (y) { n -= 2; x = y; }
139 y = x >> 1; if (y) { n -= 1; x = y; }
140 return (int) (n - x);
141 }
142
143 #ifdef ZINT_TEST /* Wrapper for direct testing */
144 INTERNAL int clz_u64_test(uint64_t x) {
145 return clz_u64(x);
146 }
147 #endif
148
149 /* Divide 128-bit dividend `t` by 64-bit divisor `v`, returning 64-bit remainder
150 * See Jacob `divmod128by128/64()` and Warren Section 9–2 (divmu64.c.txt)
151 * Note digits are 32-bit parts */
152 INTERNAL uint64_t large_div_u64(large_uint *t, uint64_t v) {
153 const uint64_t b = 0x100000000; /* Number base (2**32) */
154 uint64_t qhi = 0; /* High digit of returned quotient */
155
156 uint64_t tnhi, tnlo, tnlo1, tnlo0, vn1, vn0; /* Normalized forms of (parts of) t and v */
157 uint64_t rnhilo1; /* Remainder after dividing 1st 3 digits of t by v */
158 uint64_t qhat1, qhat0; /* Estimated quotient digits */
159 uint64_t rhat; /* Remainder of estimated quotient digit */
160 uint64_t tmp;
161 int norm_shift;
162
163 /* Deal with single-digit (i.e. 32-bit) divisor here */
164 if (v < b) {
165 qhi = t->hi / v;
166 tmp = ((t->hi - qhi * v) << 32) + (t->lo >> 32); /* k * b + tlo1 */
167 qhat1 = tmp / v;
168 tmp = ((tmp - qhat1 * v) << 32) + (t->lo & MASK32); /* k * b + tlo0 */
169 qhat0 = tmp / v;
170 t->lo = (qhat1 << 32) | qhat0;
171 t->hi = qhi;
172 return tmp - qhat0 * v;
173 }
174
175 /* Main algorithm requires t->hi < v */
176 if (t->hi >= v) {
177 qhi = t->hi / v;
178 t->hi %= v;
179 }
180
181 /* Normalize by shifting v left just enough so that its high-order
182 * bit is on, and shift t left the same amount. Note don't need extra
183 * high-end digit for dividend as t->hi < v */
184
185 norm_shift = clz_u64(v);
186 v <<= norm_shift;
187 vn1 = v >> 32;
188 vn0 = v & MASK32;
189
190 if (norm_shift > 0) {
191 tnhi = (t->hi << norm_shift) | (t->lo >> (64 - norm_shift));
192 tnlo = t->lo << norm_shift;
193 } else {
194 tnhi = t->hi;
195 tnlo = t->lo;
196 }
197
198 tnlo1 = tnlo >> 32;
199 tnlo0 = tnlo & MASK32;
200
201 /* Compute qhat1 estimate */
202
203 assert(vn1 != 0); /* Suppress clang-tidy-14 clang-analyzer-core.DivideZero */
204 qhat1 = tnhi / vn1; /* Divide first digit of v into first 2 digits of t */
205 rhat = tnhi % vn1;
206
207 /* Loop until qhat1 one digit and <= (rhat * b + 3rd digit of t) / vn0 */
208 for (tmp = qhat1 * vn0; qhat1 >= b || tmp > (rhat << 32) + tnlo1; tmp -= vn0) {
209 --qhat1;
210 rhat += vn1;
211 if (rhat >= b) { /* Must check here as (rhat << 32) would overflow */
212 break; /* qhat1 * vn0 < b * b (since vn0 < b) */
213 }
214 }
215 /* Note qhat1 will be exact as have fully divided by 2-digit divisor
216 * (can only be too high by 1 (and require "add back" step) if divisor at least 3 digits) */
217
218 /* Note high digit (if any) of both tnhi and (qhat1 * v) shifted out */
219 rnhilo1 = (tnhi << 32) + tnlo1 - (qhat1 * v);
220
221 /* Compute qhat0 estimate */
222
223 qhat0 = rnhilo1 / vn1; /* Divide first digit of v into 2-digit remains of first 3 digits of t */
224 rhat = rnhilo1 % vn1;
225
226 /* Loop until qhat0 one digit and <= (rhat * b + 4th digit of t) / vn0 */
227 for (tmp = qhat0 * vn0; qhat0 >= b || tmp > (rhat << 32) + tnlo0; tmp -= vn0) {
228 --qhat0;
229 rhat += vn1;
230 if (rhat >= b) {
231 break;
232 }
233 }
234 /* Similarly qhat0 will be exact */
235
236 t->lo = (qhat1 << 32) | qhat0;
237 t->hi = qhi;
238
239 /* Unnormalize remainder */
240 return ((rnhilo1 << 32) + tnlo0 - (qhat0 * v)) >> norm_shift;
241 }
242
243 /* Unset a bit (zero-based) */
244 INTERNAL void large_unset_bit(large_uint *t, const int bit) {
245 if (bit < 64) {
246 t->lo &= ~(((uint64_t) 1) << bit);
247 } else if (bit < 128) {
248 t->hi &= ~(((uint64_t) 1) << (bit - 64));
249 }
250 }
251
252 /* Output large_uint into an unsigned int array of size `size`, each element containing `bits` bits */
253 INTERNAL void large_uint_array(const large_uint *t, unsigned int *uint_array, const int size, int bits) {
254 int i, j;
255 uint64_t mask;
256 if (bits <= 0) {
257 bits = 8;
258 } else if (bits > 32) {
259 bits = 32;
260 }
261 mask = ~(((uint64_t) -1) << bits);
262 for (i = 0, j = 0; i < size && j < 64; i++, j += bits) {
263 uint_array[size - 1 - i] = (unsigned int) ((t->lo >> j) & mask); /* Little-endian order */
264 }
265 if (i < size) {
266 if (j != 64) {
267 j -= 64;
268 /* (first j bits of t->hi) << (bits - j) | (last (bits - j) bits of t->lo) */
269 uint_array[size - i] = (unsigned int) (((t->hi & ~((((uint64_t) -1) << j))) << (bits - j))
270 | (t->lo >> (64 - (bits - j)) & mask));
271 } else {
272 j = 0;
273 }
274 for (; i < size && j < 64; i++, j += bits) {
275 uint_array[size - 1 - i] = (unsigned int) ((t->hi >> j) & mask);
276 }
277 if (i < size) {
278 memset(uint_array, 0, sizeof(unsigned int) * (size - i));
279 }
280 }
281 }
282
283 /* As `large_uint_array()` above, except output to unsigned char array */
284 INTERNAL void large_uchar_array(const large_uint *t, unsigned char *uchar_array, const int size, int bits) {
285 int i;
286 unsigned int *uint_array = (unsigned int *) z_alloca(sizeof(unsigned int) * (size ? size : 1));
287
288 large_uint_array(t, uint_array, size, bits);
289
290 for (i = 0; i < size; i++) {
291 uchar_array[i] = (unsigned char) uint_array[i];
292 }
293 }
294
295 /* Format large_uint into buffer, which should be at least 35 chars in size */
296 INTERNAL char *large_dump(const large_uint *t, char *buf) {
297 unsigned int tlo1 = (unsigned int) (large_lo(t) >> 32);
298 unsigned int tlo0 = (unsigned int) (large_lo(t) & MASK32);
299 unsigned int thi1 = (unsigned int) (large_hi(t) >> 32);
300 unsigned int thi0 = (unsigned int) (large_hi(t) & MASK32);
301
302 if (thi1) {
303 sprintf(buf, "0x%X%08X%08X%08X", thi1, thi0, tlo1, tlo0);
304 } else if (thi0) {
305 sprintf(buf, "0x%X%08X%08X", thi0, tlo1, tlo0);
306 } else if (tlo1) {
307 sprintf(buf, "0x%X%08X", tlo1, tlo0);
308 } else {
309 sprintf(buf, "0x%X", tlo0);
310 }
311 return buf;
312 }
313
314 /* Output formatted large_uint to stdout */
315 INTERNAL void large_print(const large_uint *t) {
316 char buf[35]; /* 2 (0x) + 32 (hex) + 1 */
317
318 puts(large_dump(t, buf));
319 }
320
321 /* vim: set ts=4 sw=4 et : */