1 : /* -*- mode: C -*-
2 : *
3 : * File: pdf-types.c
4 : * Date: Sun Feb 10 21:33:44 2008
5 : *
6 : * GNU PDF Library - Basic Types Module
7 : *
8 : */
9 :
10 : /* Copyright (C) 2008, 2009, 2010 Free Software Foundation, Inc */
11 :
12 : /* This program is free software: you can redistribute it and/or modify
13 : * it under the terms of the GNU General Public License as published by
14 : * the Free Software Foundation, either version 3 of the License, or
15 : * (at your option) any later version.
16 : *
17 : * This program is distributed in the hope that it will be useful,
18 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 : * GNU General Public License for more details.
21 : *
22 : * You should have received a copy of the GNU General Public License
23 : * along with this program. If not, see <http://www.gnu.org/licenses/>.
24 : */
25 :
26 : #include <config.h>
27 :
28 : #include <pdf-types.h>
29 : #include <pdf-alloc.h>
30 :
31 :
32 : #ifndef PDF_USE_BUILTIN_64BIT_SUPPORT
33 :
34 : /* Macro used to make a safe assignment to an indirected variable. If
35 : the pointer is NULL then it is a no-op */
36 : #define ASSIGN_SAFE(p, val) \
37 : if ((p) != NULL) \
38 : { \
39 : *(p) = (val); \
40 : }
41 :
42 :
43 : pdf_i64_t
44 : pdf_i64_new (const pdf_i32_t high,
45 : const pdf_u32_t low)
46 1028411 : {
47 : pdf_i64_t pdfint;
48 1028411 : pdfint.high = high;
49 1028411 : pdfint.low = low;
50 1028411 : return pdfint;
51 : }
52 :
53 :
54 :
55 : void
56 : pdf_i64_assign (pdf_i64_t *bignum,
57 : const pdf_i32_t high,
58 : const pdf_u32_t low,
59 : pdf_status_t *p_status)
60 2992284 : {
61 2992284 : if (bignum != NULL)
62 : {
63 2992283 : bignum->high = high;
64 2992283 : bignum->low = low;
65 :
66 2992283 : ASSIGN_SAFE(p_status, PDF_OK);
67 : }
68 : else
69 : {
70 1 : ASSIGN_SAFE(p_status, PDF_EBADDATA);
71 : }
72 2992284 : }
73 :
74 : void
75 : pdf_i64_assign_quick (pdf_i64_t *bignum,
76 : const pdf_i32_t value,
77 : pdf_status_t *p_status)
78 896218 : {
79 896218 : ASSIGN_SAFE(p_status, PDF_OK);
80 :
81 896218 : if (bignum != NULL)
82 : {
83 896217 : if (value < 0)
84 : {
85 21937 : bignum->high = 0xFFFFFFFF;
86 : }
87 : else
88 : {
89 874280 : bignum->high = 0;
90 : }
91 896217 : bignum->low = value;
92 : }
93 : else
94 : {
95 1 : ASSIGN_SAFE(p_status, PDF_EBADDATA);
96 : }
97 896218 : }
98 :
99 :
100 : void
101 : pdf_i64_copy (const pdf_i64_t orig,
102 : pdf_i64_t *copy,
103 : pdf_status_t *p_status)
104 191836 : {
105 191836 : ASSIGN_SAFE(p_status, PDF_OK);
106 :
107 191836 : if (copy != NULL)
108 : {
109 191834 : copy->high = orig.high;
110 191834 : copy->low = orig.low;
111 : }
112 : else
113 : {
114 2 : ASSIGN_SAFE(p_status, PDF_EBADDATA);
115 : }
116 191836 : }
117 :
118 : void
119 : pdf_i64_add (pdf_i64_t *dest,
120 : const pdf_i64_t addend1,
121 : const pdf_i64_t addend2,
122 : pdf_status_t *p_status)
123 1328627 : {
124 1328627 : pdf_u32_t carry = 0; /*carry*/
125 : pdf_u32_t low1, low2, high1, high2;
126 :
127 1328627 : ASSIGN_SAFE(p_status, PDF_OK);
128 :
129 1328627 : if (dest != NULL)
130 : {
131 : /* We divide the unsigned 32 bit number and the signed 32 bit
132 : numbers in two 16 bit ones each to be able to manage the
133 : intermediate storage. Hence, low1 and low2 will save the two
134 : 16 bit numbers. Method based on algorithm in Knuth volume 2 */
135 :
136 : /* First 16 bit */
137 1328625 : low1 = ((addend1.low & (0x0000FFFF)) + (addend2.low & (0x0000FFFF)))
138 : % PDF_U16_DIV;
139 1328625 : carry = ((addend1.low & (0x0000FFFF)) + (addend2.low & (0x0000FFFF)))
140 : / PDF_U16_DIV;
141 :
142 : /* Second 16 bit */
143 1328625 : low2 = (carry +
144 : ((addend1.low & 0xFFFF0000)>>16) + ((addend2.low & 0xFFFF0000)>>16))
145 : % PDF_U16_DIV;
146 1328625 : carry = (carry +
147 : ((addend1.low & 0xFFFF0000)>>16) + ((addend2.low & 0xFFFF0000)>>16))
148 : / PDF_U16_DIV;
149 1328625 : dest->low = low1 + (low2<<16);
150 :
151 1328625 : high1 = (carry + (addend1.high & (0x0000FFFF)) + (addend2.high & (0x0000FFFF)))
152 : % PDF_U16_DIV;
153 1328625 : carry = (carry + (addend1.high & (0x0000FFFF)) + (addend2.high & (0x0000FFFF)))
154 : / PDF_U16_DIV;
155 1328625 : high2 = (carry +
156 : ((addend1.high & 0xFFFF0000)>>16) + ((addend2.high & 0xFFFF0000)>>16))
157 : % PDF_U16_DIV;
158 1328625 : dest->high = high1 + (high2<<16);
159 : }
160 : else
161 : {
162 2 : ASSIGN_SAFE(p_status, PDF_EBADDATA);
163 : }
164 1328627 : }
165 :
166 : int
167 : pdf_i64_cmp (const pdf_i64_t number_1,
168 : const pdf_i64_t number_2)
169 1423094 : {
170 1423094 : if (number_1.high > number_2.high)
171 : {
172 7 : return 1;
173 : }
174 1423087 : else if (number_1.high < number_2.high)
175 : {
176 17 : return -1;
177 : }
178 : else
179 : {
180 1423070 : if (number_1.low > number_2.low)
181 : {
182 839104 : return 1;
183 : }
184 : else
185 : {
186 583966 : if (number_1.low < number_2.low)
187 : {
188 131276 : return -1;
189 : }
190 : else
191 : {
192 452690 : return 0;
193 : }
194 : }
195 : }
196 : }
197 :
198 : void
199 : pdf_i64_abs (pdf_i64_t *dest,
200 : const pdf_i64_t number,
201 : pdf_status_t *p_status)
202 955873 : {
203 :
204 : pdf_i64_t temp, one;
205 :
206 955873 : ASSIGN_SAFE(p_status, PDF_OK);
207 :
208 955873 : if (dest != NULL)
209 : {
210 955872 : if (number.high < 0)
211 : {
212 15 : pdf_i64_assign(&temp,number.high,number.low, p_status);
213 15 : pdf_i64_assign(&one,0,1, p_status);
214 15 : pdf_i64_assign(dest,0,0, p_status);
215 15 : temp.high = ~temp.high;
216 15 : temp.low = ~temp.low;
217 15 : pdf_i64_add(dest, temp, one, p_status);
218 : }
219 : else
220 : {
221 955857 : pdf_i64_assign(dest, number.high, number.low, p_status);
222 : }
223 : }
224 : else
225 : {
226 1 : ASSIGN_SAFE(p_status, PDF_EBADDATA);
227 : }
228 955873 : }
229 :
230 : void
231 : pdf_i64_neg (pdf_i64_t *dest,
232 : const pdf_i64_t number,
233 : pdf_status_t *p_status)
234 315267 : {
235 : pdf_i64_t tempo;
236 : pdf_i64_t one;
237 :
238 315267 : ASSIGN_SAFE(p_status, PDF_OK);
239 :
240 315267 : if (dest != NULL)
241 : {
242 315266 : pdf_i64_assign(&tempo,0,0, p_status);
243 315266 : pdf_i64_assign(&one,0,1, p_status);
244 :
245 315266 : tempo.high = ~number.high;
246 315266 : tempo.low = ~number.low;
247 :
248 315266 : pdf_i64_add(dest, tempo, one, p_status);
249 : }
250 : else
251 : {
252 1 : ASSIGN_SAFE(p_status, PDF_EBADDATA);
253 : }
254 315267 : }
255 :
256 : void
257 : pdf_i64_subtraction (pdf_i64_t *dest,
258 : const pdf_i64_t minuend,
259 : const pdf_i64_t subtrahend,
260 : pdf_status_t *p_status)
261 315256 : {
262 : pdf_i64_t neg_subtrahend;
263 :
264 315256 : ASSIGN_SAFE(p_status, PDF_OK);
265 :
266 315256 : if (dest != NULL)
267 : {
268 315254 : pdf_i64_neg(&neg_subtrahend, subtrahend, p_status);
269 315254 : pdf_i64_add(dest, minuend, neg_subtrahend, p_status);
270 : }
271 : else
272 : {
273 2 : ASSIGN_SAFE(p_status, PDF_EBADDATA);
274 : }
275 315256 : }
276 :
277 : void
278 : shift_right (pdf_i64_t *dest)
279 0 : {
280 0 : dest->low >>= 1;
281 :
282 0 : if((0x00000001 & dest->high) == 1)
283 : {
284 0 : if ((0x80000000 & dest->low) == 0)
285 : {
286 0 : dest->low = ( dest->low | 0x80000000);
287 : }
288 : }
289 : else
290 : {
291 : if ((0x80000000 & dest->low) == 1)
292 : {
293 : dest->low = (dest->low & 0x7FFFFFFF);
294 : }
295 : }
296 :
297 0 : dest->high >>= 1;
298 0 : }
299 :
300 : void
301 : shift_right_long(pdf_i64_t *dest_high,
302 : pdf_i64_t *dest_low)
303 0 : {
304 0 : if ((dest_high == NULL) || (dest_low == NULL))
305 : {
306 0 : return;
307 : }
308 :
309 0 : shift_right(dest_low);
310 :
311 0 : if((0x00000001 & dest_high->low) == 1)
312 : {
313 0 : if ((0x80000000 & dest_low->high) == 0)
314 : {
315 0 : dest_low->high = (dest_low->high | 0x80000000);
316 : }
317 : }
318 : else
319 : {
320 : if ((0x80000000 & dest_low->high) == 1)
321 : {
322 : dest_low->high = (dest_low->high & 0x7FFFFFFF);
323 : }
324 : }
325 :
326 0 : shift_right(dest_high);
327 : }
328 :
329 : void
330 : add_long (pdf_i64_t *P1,
331 : pdf_i64_t *P2,
332 : pdf_i64_t *P3,
333 : pdf_i64_t A1,
334 : pdf_i64_t A2,
335 : pdf_i64_t A3)
336 0 : {
337 : pdf_i64_t carry;
338 0 : pdf_status_t p_status = PDF_OK;
339 :
340 0 : if ((P1 == NULL) || (P2 == NULL) || (P3 == NULL))
341 : {
342 : return;
343 : }
344 :
345 0 : pdf_i64_add(P3, *P3, A3, &p_status);
346 0 : if (P3->low == 2)
347 : {
348 : pdf_i64_t one;
349 0 : pdf_i64_assign(&one, 0, 1, &p_status);
350 0 : P3->low = 1;
351 0 : pdf_i64_add(P2, *P2, one, &p_status);
352 : }
353 :
354 0 : pdf_i64_add(P2, *P2, A2, &p_status);
355 0 : if (p_status != PDF_OK)
356 : {
357 0 : pdf_i64_assign(&carry, 0 , 1, &p_status);
358 : }
359 :
360 0 : pdf_i64_add(P3, *P3, carry, &p_status);
361 0 : pdf_i64_add(P3, *P3, A3, &p_status);
362 : }
363 :
364 : void
365 : pdf_i64_mult (pdf_i64_t *dest,
366 : const pdf_i64_t factor_1,
367 : const pdf_i64_t factor_2,
368 : pdf_status_t *p_status)
369 397581 : {
370 : int i, j;
371 : /* Variables follow the nomenclature of the algorithm
372 : presented in Knuth vol 2.
373 :
374 : k is the carry bit, t is a variable used to save partial results,
375 : the mask is used to tranfer data from arrays to pdf_i64_t types,
376 : and cont is a simple counter */
377 : pdf_u32_t mask, t , k;
378 : pdf_i64_t multiplier, multiplicand;
379 : /* The result is stored in w */
380 397581 : pdf_u32_t w[] ={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
381 : /* v is an array where the multiplier is stored, and u is where the
382 : multiplicand is stored*/
383 : pdf_u32_t v[8], u[8];
384 397581 : int result_sign = 1; /* Used to carry the sign of the result till the end */
385 : pdf_i64_t zero; /* Used to store zero value in pdf_i64_t format */
386 : pdf_i64_t temp; /* Variable used to save partial results */
387 :
388 397581 : ASSIGN_SAFE(p_status, PDF_OK);
389 :
390 397581 : if (dest != NULL)
391 : {
392 397580 : pdf_i64_abs (&multiplicand, factor_1, p_status);
393 397580 : pdf_i64_abs (&multiplier, factor_2, p_status);
394 :
395 : /*Knuth vol 2 method*/
396 :
397 : /* Now check the signs of multiplier and multiplicand */
398 397580 : pdf_i64_assign(&zero,0,0, p_status);
399 :
400 397580 : if (pdf_i64_cmp(factor_1,zero) < 0)
401 : {
402 2 : result_sign = -1;
403 2 : pdf_i64_abs(&multiplier,multiplier, p_status);
404 : }
405 :
406 397580 : if (pdf_i64_cmp(factor_2,zero) < 0)
407 : {
408 1 : pdf_i64_abs(&multiplicand,multiplicand, p_status);
409 :
410 1 : if (result_sign == -1)
411 : {
412 1 : result_sign = 1;
413 : }
414 : else
415 : {
416 0 : result_sign = -1;
417 : }
418 : }
419 :
420 397580 : mask = 0xFF000000;
421 3578220 : for (i = 0; i < 8;i++)
422 : {
423 3180640 : if (i <= 3)
424 : {
425 1590320 : v[i] = ((multiplier.high & (mask >> (i * 8))) >> ((3 - i) * 8));
426 : }
427 : else
428 : {
429 1590320 : v[i] = ((multiplier.low & (mask >> ((i - 4) * 8))) >> ( (7 - i) * 8));
430 : }
431 : }
432 :
433 3578220 : for (i = 0; i < 8;i++)
434 : {
435 3180640 : if (i <= 3)
436 : {
437 1590320 : u[i] = ((multiplicand.high & (mask >> (i * 8))) >> ((3 - i) * 8));
438 : }
439 : else
440 : {
441 1590320 : u[i] = ((multiplicand.low & (mask >> ((i - 4) * 8))) >> ((7 - i) * 8));
442 : }
443 : }
444 :
445 3578220 : for (j = 7; j >= 0;j--)
446 : {
447 3180640 : k = 0;
448 28625760 : for(i = 7; i >= 0;i--)
449 : {
450 25445120 : t = u[i] * v[j] + w[i + j + 1] + k;
451 25445120 : w[i + j + 1] = t % PDF_U8_DIV;
452 25445120 : k = t / PDF_U8_DIV;
453 : }
454 : }
455 :
456 397580 : pdf_i64_assign(&temp, 0, 0, p_status);
457 3578220 : for (i = 0; i < 8;i++)
458 : {
459 3180640 : if (i <=3)
460 : {
461 1590320 : temp.high = temp.high + (w[i + 8] << (8 * (7 - i)));
462 : }
463 : else
464 : {
465 1590320 : temp.low = temp.low + (w[i + 8] << (8 * (7 - i)));
466 : }
467 : }
468 :
469 : /* Accomodate final result to the sign of the multiplicand and
470 : multiplier */
471 397580 : if (result_sign == -1)
472 : {
473 1 : pdf_i64_neg(dest, temp, p_status);
474 : }
475 : else
476 : {
477 397579 : pdf_i64_assign(dest, temp.high, temp.low, p_status);
478 : }
479 : }
480 : else
481 : {
482 1 : ASSIGN_SAFE(p_status, PDF_EBADDATA);
483 : }
484 397581 : }
485 :
486 : void
487 : mult_long (pdf_u32_t *w,
488 : pdf_i64_t factor_1,
489 : pdf_i64_t factor_2)
490 80348 : {
491 : /*Knuth vol 2 method*/
492 :
493 : int i, j;
494 : pdf_u32_t mask, t , k;
495 : pdf_i64_t multiplier, multiplicand;
496 : pdf_status_t p_status;
497 80348 : pdf_i64_abs(&multiplicand, factor_1, &p_status);
498 80348 : pdf_i64_abs(&multiplier, factor_2, &p_status);
499 : pdf_u32_t v[8], u[8];
500 :
501 80348 : if (w == NULL)
502 : {
503 0 : return;
504 : }
505 :
506 1365916 : for (i = 0;i < 16;i++)
507 : {
508 1285568 : w[i] = 0;
509 : }
510 :
511 80348 : mask = 0xFF000000;
512 723132 : for (i = 0; i < 8;i++)
513 : {
514 642784 : if (i <= 3)
515 : {
516 321392 : v[i] = ((multiplier.high & (mask >> (i * 8))) >> ((3 - i) * 8));
517 : }
518 : else
519 : {
520 321392 : v[i] = ((multiplier.low & (mask >> ((i - 4) * 8))) >> ((7 - i) * 8));
521 : }
522 : }
523 :
524 723132 : for (i = 0; i < 8;i++)
525 : {
526 642784 : if (i <= 3)
527 : {
528 321392 : u[i] = ((multiplicand.high & (mask >> (i * 8))) >> ((3 - i) * 8));
529 : }
530 : else
531 : {
532 321392 : u[i] = ((multiplicand.low & (mask >> ((i - 4) * 8))) >> ((7 - i) * 8));
533 : }
534 : }
535 :
536 :
537 723132 : for (j = 7; j >= 0;j--)
538 : {
539 642784 : k = 0;
540 5785056 : for(i = 7; i >= 0;i--)
541 : {
542 5142272 : t = u[i] * v[j] + w[i + j + 1] + k;
543 5142272 : w[i + j + 1] = t % PDF_U8_DIV;
544 5142272 : k = t / PDF_U8_DIV;
545 : }
546 : }
547 :
548 :
549 : }
550 :
551 :
552 : void
553 : pdf_i64_div (pdf_i64_t *dest,
554 : const pdf_i64_t const_dividend,
555 : const pdf_i64_t const_divisor,
556 : pdf_status_t *p_status)
557 53567 : {
558 : /*Knuth method*/
559 :
560 : int i, j; /*counters*/
561 : /*k is used to find the first non-zero digit in the divisor, q_bar
562 : is where the partial result of the division is stored, z is used to find
563 : the highest non-zero digit in the dividend*/
564 : /*See Knuth for definitions of m and n*/
565 : pdf_u32_t k, q_bar, n, z;
566 : pdf_i32_t m;
567 : /*divisor_nor stores normalised divisor, d_pdf is used to
568 : normalise divisor and dividend, v_pdf is the internal pdf_i64_t
569 : version of divisor, q_bar_pdf is the pdf_i64_t version of the
570 : partial division result, temp is a temporary variable used int
571 : the procedures*/
572 : pdf_i64_t divisor_nor, d_pdf,v_pdf, q_bar_pdf, temp;
573 : pdf_i64_t divisor;
574 : pdf_i64_t dividend;
575 : pdf_u32_t v[8]; /*where divisor is stored*/
576 : /*q is where result is stored, u is where the dividend is stored,
577 : and temporal is a temporal vector used in the different procedures*/
578 53567 : pdf_u32_t q[8] = {0, 0, 0, 0, 0, 0, 0, 0}, u[16], temporal[8];
579 : pdf_u32_t d; /*used to normalise divisor and dividend*/
580 53567 : pdf_u32_t b = PDF_U8_DIV; /*base of the division*/
581 53567 : pdf_u32_t mask = 0xFF000000; /*mask used to pass info from pdf_i64_t types and arrays*/
582 53567 : pdf_i64_t zero = pdf_i64_new(0 , 0); /*zero in pdf_i64_t format*/
583 53567 : int result_sign = 1; /*used to carry the sign of the result till the end*/
584 :
585 53567 : ASSIGN_SAFE(p_status, PDF_OK);
586 :
587 53567 : if (dest != NULL)
588 : {
589 53566 : z = 0;
590 53566 : k = 0;
591 :
592 : /* Make a non-const divisor */
593 53566 : divisor = pdf_i64_new (0, 0);
594 53566 : pdf_i64_copy (const_divisor, &divisor, p_status);
595 : /* Make a non-const dividend */
596 53566 : dividend = pdf_i64_new (0, 0);
597 53566 : pdf_i64_copy (const_dividend, ÷nd, p_status);
598 :
599 : /*Check first if divisor != 0*/
600 53566 : if (pdf_i64_cmp(zero,divisor) == 0)
601 : {
602 0 : ASSIGN_SAFE(p_status, PDF_EDIVBYZERO);
603 : return;
604 : }
605 : /*Now check the signs fo divisor and dividend*/
606 53566 : if (pdf_i64_cmp(divisor,zero) < 0)
607 : {
608 3 : result_sign = -1;
609 3 : pdf_i64_abs(&divisor,divisor, p_status);
610 : }
611 53566 : if (pdf_i64_cmp(dividend,zero) < 0)
612 : {
613 3 : pdf_i64_abs(÷nd,dividend, p_status);
614 3 : if (result_sign == -1)
615 : {
616 1 : result_sign = 1;
617 : }
618 : else
619 : {
620 2 : result_sign = -1;
621 : }
622 : }
623 :
624 : /*We check if abs(divisor) > abs(dividend)*/
625 53566 : if (pdf_i64_cmp(divisor, dividend) == 1)
626 : {
627 21162 : pdf_i64_assign(dest,0,0, p_status);
628 : }
629 :
630 :
631 : /*we store divisor in array*/
632 482094 : for (i = 0; i < 8;i++)
633 : {
634 428528 : if (i <= 3)
635 : {
636 214264 : v[i] = ((divisor.high & (mask >> (i * 8))) >> ((3 - i) * 8)) ;
637 : }
638 : else
639 : {
640 214264 : v[i] = ((divisor.low & (mask >> ((i - 4) * 8))) >> ((7 - i) * 8));
641 : }
642 : }
643 :
644 : /*we store dividend in temporal array*/
645 482094 : for (i = 0; i < 8;i++)
646 : {
647 428528 : if (i <= 3)
648 : {
649 214264 : temporal[i] = ((dividend.high & (mask >> (i * 8))) >> ((3 - i) * 8)) ;
650 : }
651 : else
652 : {
653 214264 : temporal[i] = ((dividend.low & (mask >> ((i - 4) * 8))) >> ((7 - i) * 8));
654 : }
655 : }
656 : /*With z we'll find the highest non-zero 8 bit number in the dividend*/
657 482094 : for (i = 7; i >= 0; i--)
658 : {
659 428528 : if (temporal[i] != 0)
660 : {
661 99183 : z = i;
662 : }
663 : }
664 :
665 :
666 : /*with k we'll find the highest non-zero 8 bit number in the divisor*/
667 482094 : for (i = 7; i >= 0; i--)
668 : {
669 428528 : if (v[i] != 0)
670 : {
671 107122 : k = i;
672 : }
673 : }
674 :
675 : /*With z and k the relative sizes of the different numbers are found.
676 : See Knuth algorithm for more details on n and m.*/
677 :
678 53566 : n = 8 - k; /*n = size of non zero v*/
679 53566 : m = k - z;
680 :
681 :
682 : /*d is used to normalise divisor and dividend; see Knuth for details*/
683 53566 : d = b/(v[k] + 1);
684 :
685 :
686 : /*we store d in pdf_i64_t type*/
687 53566 : d_pdf = pdf_i64_new(0, d);
688 :
689 : /*Here u and v are multiplied by d to normalise them*/
690 :
691 : /*we use a extra long version of pdf_i64_t multiplication to avoid
692 : unwanted overflows*/
693 : /*normalised dividend is stored in variable u*/
694 53566 : mult_long(u, dividend, d_pdf);
695 : /*normalised divisor is stored in varialbe divisor_d*/
696 53566 : pdf_i64_mult(&divisor_nor, divisor, d_pdf, p_status);
697 :
698 : /*We add up 8 to z to adapt it to the new 16 bit array, but
699 : 1 is subtracted due to the inclusion of Uo. See Knuth vol2
700 : for more details on Uo*/
701 :
702 53566 : z = z + 7;
703 :
704 :
705 :
706 : /*normalised divisor is stored in array v*/
707 482094 : for (i = 0; i < 8;i++)
708 : {
709 428528 : if (i <= 3)
710 : {
711 214264 : v[i] = ((divisor_nor.high & (mask >> (i * 8))) >> ((3 - i) * 8));
712 : }
713 : else
714 : {
715 214264 : v[i] = ((divisor_nor.low & (mask >> ((i - 4) * 8))) >> ((7 - i) * 8));
716 : }
717 : }
718 :
719 :
720 :
721 : /*With u and v normalised we start the algorithm*/
722 : /*Always add z when going through u array to get rid of non-useful zeros*/
723 : /*The different steps follow the algorithm described in Knuth vol 2*/
724 258971 : for (j = 0;j <= m; j++)
725 : {
726 : /*Step D3*/
727 205405 : if (u[j + z] == v[k])
728 : {
729 298 : q_bar = b - 1;
730 : }
731 : else
732 : {
733 205107 : q_bar = (u[j + z] * b + u[j + z + 1])/v[k];
734 : }
735 205405 : if (k < 7)
736 : {
737 87870 : while (v[k + 1] * q_bar >
738 : ((u[j + z] * b + u[j + z + 1] - q_bar * v[k] ) * b + u[j + z + 2] ))
739 : {
740 11889 : q_bar = q_bar - 1;
741 : }
742 : }
743 :
744 : /*Step D4*/
745 : /*We put q_bar into a i64 type to be able to multiply it by the normalised divisor*/
746 205405 : q_bar_pdf = pdf_i64_new(0, q_bar);
747 205405 : pdf_i64_mult(&v_pdf, divisor_nor, q_bar_pdf, p_status);
748 : /*put u[j]...u[j + n] into a pdf_i64_t type and subtract v_pdf*/
749 205405 : temp = pdf_i64_new(0,0);
750 768177 : for (i = j + n; i >= j; i--)
751 : {
752 562772 : int kk = j + n -3;
753 562772 : if (i >= kk)
754 : {
755 562772 : temp.low = temp.low + (u[i + z] << (8 * (j + n - i)));
756 : }
757 : else
758 : {
759 0 : temp.high = temp.high + (u[i + z] << (8 * (j + n - i)));
760 : }
761 : }
762 :
763 205405 : pdf_i64_subtraction(&temp, temp, v_pdf, p_status);
764 :
765 : /*We finally put q_bar in the results array*/
766 205405 : q[j] = q_bar;
767 : /*If the remainder is less than zero then we re-add the divisor and subtract one from q
768 : Step D6*/
769 205405 : if (pdf_i64_cmp(temp, zero) < 0)
770 : {
771 0 : q[j] = q[j] - 1;
772 0 : pdf_i64_add(&temp, divisor_nor, temp, p_status);
773 : }
774 : /*Step D5; uj...uj+n is substituted with the uj...uj+n obtained above*/
775 :
776 1848645 : for (i = 0; i < 8;i++)
777 : {
778 1643240 : if (i <= 3)
779 : {
780 821620 : temporal[i] = ((temp.high & (mask >> (i * 8))) >> ((3 - i) * 8)) ;
781 : }
782 : else
783 : {
784 821620 : temporal[i] = ((temp.low & (mask >> ((i - 4) * 8))) >> ((7 - i) * 8));
785 : }
786 : }
787 :
788 1848645 : for (i = 7; i >= 0;i--)
789 : {
790 1643240 : u[z + j + n - 7 + i] = temporal[i];
791 : }
792 : }/*end of for in j*/
793 :
794 :
795 53566 : pdf_i64_assign(&temp,0,0, p_status);
796 :
797 258971 : for (i = m; i >= 0; i--)
798 : {
799 205405 : if (m > 3)
800 : {
801 136616 : if (i >= (m -3))
802 : {
803 75688 : temp.low = temp.low + (q[i] << (8* (m - i)));
804 : }
805 : else
806 : {
807 60928 : temp.high = temp.high + (q[i] << (8* (m - i - 4)));
808 : }
809 : }
810 : else
811 : {
812 68789 : temp.low = temp.low + (q[i] << (8* (m - i)));
813 : }
814 : }
815 :
816 53566 : if (result_sign == -1)
817 : {
818 4 : pdf_i64_neg(dest, temp, p_status);
819 : }
820 : else
821 : {
822 53562 : pdf_i64_assign(dest, temp.high, temp.low, p_status);
823 : }
824 : }
825 : else
826 : {
827 1 : ASSIGN_SAFE(p_status, PDF_EBADDATA);
828 : }
829 : }
830 :
831 : void
832 : pdf_i64_mod(pdf_i64_t *dest,
833 : const pdf_i64_t const_dividend,
834 : const pdf_i64_t const_divisor,
835 : pdf_status_t *p_status)
836 26784 : {
837 : /*Knuth method*/
838 :
839 : int i, j; /*counters*/
840 : /*k is used to find the first non-zero digit in the divisor, q_bar
841 : is where the partial result of the division is stored, z is used to find
842 : the highest non-zero digit in the dividend*/
843 : /*See Knuth for definitions of m and n*/
844 : pdf_u32_t k, q_bar, n, z;
845 : pdf_i32_t m;
846 : /*divisor_nor stores normalised divisor, d_pdf is used to
847 : normalise divisor and dividend, v_pdf is the internal pdf_i64_t
848 : version of divisor, q_bar_pdf is the pdf_i64_t version of the
849 : partial division result, temp is a temporary variable used int
850 : the procedures*/
851 : pdf_i64_t divisor_nor, d_pdf,v_pdf, q_bar_pdf, temp;
852 : pdf_i64_t divisor;
853 : pdf_i64_t dividend;
854 : pdf_u32_t v[8]; /*where divisor is stored*/
855 : /*q is where result is stored, u is where the dividend is stored,
856 : and temporal is a temporal vector used in the different procedures*/
857 26784 : pdf_u32_t q[8] = {0, 0, 0, 0, 0, 0, 0, 0}, u[16], temporal[8];
858 : pdf_u32_t d; /*used to normalise divisor and dividend*/
859 26784 : pdf_u32_t b = PDF_U8_DIV; /*base of the division*/
860 26784 : pdf_u32_t mask = 0xFF000000; /*mask used to pass info from pdf_i64_t types and arrays*/
861 26784 : pdf_i64_t zero = pdf_i64_new(0 , 0); /*zero in pdf_i64_t format*/
862 26784 : int result_sign = 1; /*used to carry the sign of the result till the end*/
863 :
864 26784 : ASSIGN_SAFE(p_status, PDF_OK);
865 :
866 26784 : if (dest != NULL)
867 : {
868 :
869 26782 : z = 0;
870 26782 : k = 0;
871 :
872 : /* Make a non-const divisor */
873 26782 : divisor = pdf_i64_new (0, 0);
874 26782 : pdf_i64_copy (const_divisor, &divisor, p_status);
875 : /* Make a non-const dividend */
876 26782 : dividend = pdf_i64_new (0, 0);
877 26782 : pdf_i64_copy (const_dividend, ÷nd, p_status);
878 :
879 : /*Check first if divisor != 0*/
880 26782 : if (pdf_i64_cmp(zero,divisor) == 0)
881 : {
882 0 : ASSIGN_SAFE(p_status, PDF_EDIVBYZERO);
883 : return;
884 : }
885 : /*Now check the signs fo divisor and dividend*/
886 26782 : if (pdf_i64_cmp(divisor,zero) < 0)
887 : {
888 2 : pdf_i64_abs(&divisor,divisor, p_status);
889 : }
890 26782 : if (pdf_i64_cmp(dividend,zero) < 0)
891 : {
892 3 : pdf_i64_abs(÷nd,dividend, p_status);
893 3 : result_sign = -1;
894 : }
895 :
896 : /*We check if abs(divisor) > abs(dividend)*/
897 26782 : if (pdf_i64_cmp(divisor, dividend) == 1)
898 : {
899 9619 : pdf_i64_assign(dest,0,0, p_status);
900 : }
901 :
902 : /*we store divisor in array*/
903 241038 : for (i = 0; i < 8;i++)
904 : {
905 214256 : if (i <= 3)
906 : {
907 107128 : v[i] = ((divisor.high & (mask >> (i * 8))) >> ((3 - i) * 8)) ;
908 : }
909 : else
910 : {
911 107128 : v[i] = ((divisor.low & (mask >> ((i - 4) * 8))) >> ((7 - i) * 8));
912 : }
913 : }
914 :
915 : /*we store dividend in temporal array*/
916 241038 : for (i = 0; i < 8;i++)
917 : {
918 214256 : if (i <= 3)
919 : {
920 107128 : temporal[i] = ((dividend.high & (mask >> (i * 8))) >> ((3 - i) * 8)) ;
921 : }
922 : else
923 : {
924 107128 : temporal[i] = ((dividend.low & (mask >> ((i - 4) * 8))) >> ((7 - i) * 8));
925 : }
926 : }
927 : /*With z we'll find the highest non-zero 8 bit number in the dividend*/
928 241038 : for (i = 7; i >= 0; i--)
929 : {
930 214256 : if (temporal[i] != 0)
931 : {
932 67555 : z = i;
933 : }
934 : }
935 :
936 : /*with k we'll find the highest non-zero 8 bit number in the divisor*/
937 241038 : for (i = 7; i >= 0; i--)
938 : {
939 214256 : if (v[i] != 0)
940 : {
941 80336 : k = i;
942 : }
943 : }
944 :
945 : /*With z and k the relative sizes of the different numbers are found.
946 : See Knuth algorithm for more details on n and m.*/
947 :
948 26782 : n = 8 - k; /*n = size of non zero v*/
949 26782 : m = k - z;
950 :
951 : /*d is used to normalise divisor and dividend; see Knuth for details*/
952 26782 : d = b/(v[k] + 1);
953 :
954 : /*we store d in pdf_i64_t type*/
955 26782 : d_pdf = pdf_i64_new(0, d);
956 :
957 : /*Here u and v are multiplied by d to normalise them*/
958 :
959 : /*we use a extra long version of pdf_i64_t multiplication to avoid
960 : unwanted overflows*/
961 : /*normalised dividend is stored in variable u*/
962 26782 : mult_long(u, dividend, d_pdf);
963 : /*normalised divisor is stored in varialbe divisor_d*/
964 26782 : pdf_i64_mult(&divisor_nor, divisor, d_pdf, p_status);
965 :
966 : /*We add up 8 to z to adapt it to the new 16 bit array, but
967 : 1 is subtracted due to the inclusion of Uo. See Knuth vol2
968 : for more details on Uo*/
969 :
970 26782 : z = z + 7;
971 :
972 : /*normalised divisor is stored in array v*/
973 241038 : for (i = 0; i < 8;i++)
974 : {
975 214256 : if (i <= 3)
976 : {
977 107128 : v[i] = ((divisor_nor.high & (mask >> (i * 8))) >> ((3 - i) * 8));
978 : }
979 : else
980 : {
981 107128 : v[i] = ((divisor_nor.low & (mask >> ((i - 4) * 8))) >> ((7 - i) * 8));
982 : }
983 : }
984 :
985 : /*With u and v normalised we start the algorithm*/
986 : /*Always add z when going through u array to get rid of non-useful zeros*/
987 : /*The different steps follow the algorithm described in Knuth vol 2*/
988 102768 : for (j = 0;j <= m; j++)
989 : {
990 : /*Step D3*/
991 75986 : if (u[j + z] == v[k])
992 : {
993 298 : q_bar = b - 1;
994 : }
995 : else
996 : {
997 75688 : q_bar = (u[j + z] * b + u[j + z + 1])/v[k];
998 : }
999 87875 : while (v[k + 1] * q_bar >((u[j + z] * b + u[j + z + 1] - q_bar * v[k] ) * b + u[j + z + 2] ))
1000 : {
1001 11889 : q_bar = q_bar - 1;
1002 : }
1003 : /*Step D4*/
1004 : /*We put q_bar into a i64 type to be able to multiply it by the normalised divisor*/
1005 75986 : q_bar_pdf = pdf_i64_new(0, q_bar);
1006 75986 : pdf_i64_mult(&v_pdf, divisor_nor, q_bar_pdf, p_status);
1007 : /*put u[j]...u[j + n] into a pdf_i64_t type and subtract v_pdf*/
1008 75986 : temp = pdf_i64_new(0,0);
1009 379920 : for (i = j + n; i >= j; i--)
1010 : {
1011 303934 : int kk = j + n -3;
1012 303934 : if (i >= kk)
1013 : {
1014 303934 : temp.low = temp.low + (u[i + z] << (8 * (j + n - i)));
1015 : }
1016 : else
1017 : {
1018 0 : temp.high = temp.high + (u[i + z] << (8 * (j + n - i)));
1019 : }
1020 : }
1021 :
1022 75986 : pdf_i64_subtraction(&temp, temp, v_pdf, p_status);
1023 : /*We finally put q_bar in the results array*/
1024 75986 : q[j] = q_bar;
1025 : /*If the remainder is less than zero then we re-add the divisor and subtract one from q
1026 : Step D6*/
1027 75986 : if (pdf_i64_cmp(temp, zero) < 0)
1028 : {
1029 0 : q[j] = q[j] - 1;
1030 0 : pdf_i64_add(&temp, divisor_nor, temp, p_status);
1031 : }
1032 : /*Step D5; uj...uj+n is substituted with the uj...uj+n obtained above*/
1033 :
1034 683874 : for (i = 0; i < 8;i++)
1035 : {
1036 607888 : if (i <= 3)
1037 : {
1038 303944 : temporal[i] = ((temp.high & (mask >> (i * 8))) >> ((3 - i) * 8)) ;
1039 : }
1040 : else
1041 : {
1042 303944 : temporal[i] = ((temp.low & (mask >> ((i - 4) * 8))) >> ((7 - i) * 8));
1043 : }
1044 : }
1045 :
1046 683874 : for (i = 7; i >= 0;i--)
1047 : {
1048 607888 : u[z + j + n - 7 + i] = temporal[i];
1049 : }
1050 : }/*end of for in j*/
1051 :
1052 26782 : pdf_i64_assign(&temp,0,0, p_status);
1053 :
1054 241038 : for (i = 0; i < 8;i++)
1055 : {
1056 214256 : if (i <=3)
1057 : {
1058 107128 : temp.high = temp.high + (u[i + 8] << (8 * (7 - i)));
1059 : }
1060 : else
1061 : {
1062 107128 : temp.low = temp.low + (u[i + 8] << (8 * (7 - i)));
1063 : }
1064 : }
1065 :
1066 26782 : if (result_sign == -1)
1067 : {
1068 : pdf_i64_t temp_sign;
1069 3 : pdf_i64_assign(&temp_sign,0,0, p_status);
1070 3 : pdf_i64_div(&temp_sign,temp,d_pdf, p_status);
1071 3 : pdf_i64_neg(dest, temp_sign, p_status);
1072 : }
1073 : else
1074 : {
1075 26779 : pdf_i64_assign(dest,0,0, p_status);
1076 26779 : pdf_i64_div(dest,temp,d_pdf, p_status);
1077 : }
1078 :
1079 : }
1080 : else
1081 : {
1082 2 : ASSIGN_SAFE(p_status, PDF_EBADDATA);
1083 : }
1084 :
1085 : }
1086 :
1087 : /* NOTE for all those functions receiving pdf_i32_t as input, where internal
1088 : * conversion to pdf_i64_t is done: We know that pdf_i64_new function doesn't
1089 : * really do memory allocation, so we could directly call pdf_i64_assign_quick.
1090 : * This is not allowed outside the basic types module, where pdf_i64_new must
1091 : * always be called. */
1092 :
1093 : /* Add a pdf_i64_t and a pdf_i32_t */
1094 : void
1095 : pdf_i64_add_i32 (pdf_i64_t *dest,
1096 : const pdf_i64_t addend1,
1097 : const pdf_i32_t addend2,
1098 : pdf_status_t *p_status)
1099 683379 : {
1100 : pdf_i64_t aux;
1101 :
1102 683379 : pdf_i64_assign_quick(&aux, addend2, p_status);
1103 683379 : pdf_i64_add(dest, addend1, aux, p_status);
1104 683379 : }
1105 :
1106 : /* Compare a pdf_i64_t and a pdf_i32_t */
1107 : int pdf_i64_cmp_i32 (const pdf_i64_t number_1,
1108 : const pdf_i32_t number_2)
1109 6 : {
1110 : pdf_i64_t aux;
1111 6 : pdf_status_t p_status = PDF_OK;
1112 :
1113 6 : pdf_i64_assign_quick(&aux, number_2, &p_status);
1114 :
1115 6 : return pdf_i64_cmp(number_1, aux);
1116 : }
1117 :
1118 :
1119 : /* Subtract a pdf_i64_t and a pdf_i32_t variable */
1120 : void
1121 : pdf_i64_subtraction_i32_min (pdf_i64_t *dest,
1122 : const pdf_i32_t minuend,
1123 : const pdf_i64_t subtrahend,
1124 : pdf_status_t *p_status)
1125 0 : {
1126 : pdf_i64_t aux;
1127 :
1128 0 : pdf_i64_assign_quick (&aux, minuend, p_status);
1129 0 : pdf_i64_subtraction (dest, aux, subtrahend, p_status);
1130 0 : }
1131 :
1132 : void
1133 : pdf_i64_subtraction_i32_sub(pdf_i64_t *dest, \
1134 : const pdf_i64_t minuend, \
1135 : const pdf_i32_t subtrahend,
1136 : pdf_status_t *p_status)
1137 0 : {
1138 : pdf_i64_t aux;
1139 :
1140 0 : pdf_i64_assign_quick (&aux, subtrahend, p_status);
1141 0 : pdf_i64_mult (dest, minuend, aux, p_status);
1142 0 : }
1143 :
1144 : /* Multiply a pdf_i64_t and a pdf_i32_t */
1145 : void
1146 : pdf_i64_mult_i32 (pdf_i64_t *dest,
1147 : const pdf_i64_t factor_1,
1148 : const pdf_i32_t factor_2,
1149 : pdf_status_t *p_status)
1150 35838 : {
1151 : pdf_i64_t aux;
1152 :
1153 35838 : pdf_i64_assign_quick (&aux, factor_2, p_status);
1154 35838 : pdf_i64_mult (dest, factor_1, aux, p_status);
1155 35838 : }
1156 :
1157 : /* Division between a pdf_i64_t and a pdf_i32_t */
1158 : void
1159 : pdf_i64_div_i32_dividend (pdf_i64_t *dest,
1160 : const pdf_i32_t dividend,
1161 : const pdf_i64_t divisor,
1162 : pdf_status_t *p_status)
1163 0 : {
1164 : pdf_i64_t aux;
1165 :
1166 0 : pdf_i64_assign_quick (&aux, dividend, p_status);
1167 0 : pdf_i64_div (dest, aux, divisor, p_status);
1168 0 : }
1169 :
1170 : void
1171 : pdf_i64_div_i32_divisor (pdf_i64_t *dest,
1172 : const pdf_i64_t dividend,
1173 : const pdf_i32_t divisor,
1174 : pdf_status_t *p_status)
1175 26777 : {
1176 : pdf_i64_t aux;
1177 :
1178 26777 : pdf_i64_assign_quick (&aux, divisor, p_status);
1179 26777 : pdf_i64_div (dest, dividend, aux, p_status);
1180 26777 : }
1181 :
1182 :
1183 : /* Modulus between a pdf_i64_t and a pdf_i32_t */
1184 : void
1185 : pdf_i64_mod_i32_dividend (pdf_i64_t *dest,
1186 : const pdf_i32_t dividend,
1187 : const pdf_i64_t divisor,
1188 : pdf_status_t *p_status)
1189 0 : {
1190 : pdf_i64_t aux;
1191 :
1192 0 : pdf_i64_assign_quick (&aux, dividend, p_status);
1193 0 : pdf_i64_mod (dest, aux, divisor, p_status);
1194 0 : }
1195 :
1196 : void
1197 : pdf_i64_mod_i32_divisor (pdf_i64_t *dest,
1198 : const pdf_i64_t dividend,
1199 : const pdf_i32_t divisor,
1200 : pdf_status_t *p_status)
1201 26777 : {
1202 : pdf_i64_t aux;
1203 :
1204 26777 : pdf_i64_assign_quick (&aux, divisor, p_status);
1205 26777 : pdf_i64_mod (dest, dividend, aux, p_status);
1206 26777 : }
1207 :
1208 : /* Get number as pdf_i32_t */
1209 : pdf_i32_t
1210 : pdf_i64_to_i32 (const pdf_i64_t bignum)
1211 53554 : {
1212 : /* From the highest 32bits, take the sign only */
1213 53554 : return ((bignum.high >= 0) ? bignum.low : (-1 * bignum.low));
1214 : }
1215 :
1216 : #endif /* !PDF_USE_BUILTIN_64BIT_SUPPORT */
1217 :
1218 : pdf_buffer_t
1219 : pdf_buffer_new (pdf_size_t size)
1220 2465 : {
1221 : pdf_buffer_t new_buf;
1222 :
1223 2465 : new_buf = pdf_alloc (sizeof(struct pdf_buffer_s));
1224 :
1225 2465 : if (new_buf != NULL)
1226 : {
1227 2465 : new_buf->data = pdf_alloc (sizeof(pdf_char_t) * size);
1228 2465 : new_buf->size = size;
1229 2465 : pdf_buffer_rewind (new_buf);
1230 : }
1231 :
1232 2465 : return new_buf;
1233 : }
1234 :
1235 : pdf_status_t
1236 : pdf_buffer_destroy (pdf_buffer_t buffer)
1237 1910 : {
1238 1910 : pdf_dealloc (buffer->data);
1239 1910 : pdf_dealloc (buffer);
1240 :
1241 1910 : return PDF_OK;
1242 : }
1243 :
1244 : pdf_bool_t
1245 : pdf_buffer_full_p (pdf_buffer_t buffer)
1246 14189 : {
1247 14189 : return (buffer->wp == buffer->size);
1248 : }
1249 :
1250 : pdf_bool_t
1251 : pdf_buffer_eob_p (pdf_buffer_t buffer)
1252 293117 : {
1253 293117 : return ((buffer->wp - buffer->rp) == 0);
1254 : }
1255 :
1256 :
1257 : pdf_status_t
1258 : pdf_buffer_resize (pdf_buffer_t buffer, pdf_size_t newsize)
1259 2 : {
1260 2 : pdf_char_t *newdata = pdf_realloc (buffer->data, newsize);
1261 2 : if (!newdata)
1262 0 : return PDF_ENOMEM;
1263 :
1264 2 : buffer->data = newdata;
1265 2 : buffer->size = newsize;
1266 2 : buffer->rp = PDF_MIN (buffer->rp, newsize);
1267 2 : buffer->wp = PDF_MIN (buffer->wp, newsize);
1268 2 : return PDF_OK;
1269 : }
1270 :
1271 :
1272 : pdf_status_t
1273 : pdf_buffer_rewind (pdf_buffer_t buffer)
1274 13730 : {
1275 13730 : buffer->rp = 0;
1276 13730 : buffer->wp = 0;
1277 :
1278 13730 : return PDF_OK;
1279 : }
1280 :
1281 :
1282 : /* End of pdf-types.c */
|
