source: trunk/poppler/freetype-2.1.10/src/base/ftcalc.c @ 2

Last change on this file since 2 was 2, checked in by Eugene Romanenko, 15 years ago

First import

File size: 13.0 KB
Line 
1/***************************************************************************/
2/*                                                                         */
3/*  ftcalc.c                                                               */
4/*                                                                         */
5/*    Arithmetic computations (body).                                      */
6/*                                                                         */
7/*  Copyright 1996-2001, 2002, 2003, 2004 by                               */
8/*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
9/*                                                                         */
10/*  This file is part of the FreeType project, and may only be used,       */
11/*  modified, and distributed under the terms of the FreeType project      */
12/*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
13/*  this file you indicate that you have read the license and              */
14/*  understand and accept it fully.                                        */
15/*                                                                         */
16/***************************************************************************/
17
18  /*************************************************************************/
19  /*                                                                       */
20  /* Support for 1-complement arithmetic has been totally dropped in this  */
21  /* release.  You can still write your own code if you need it.           */
22  /*                                                                       */
23  /*************************************************************************/
24
25  /*************************************************************************/
26  /*                                                                       */
27  /* Implementing basic computation routines.                              */
28  /*                                                                       */
29  /* FT_MulDiv(), FT_MulFix(), FT_DivFix(), FT_RoundFix(), FT_CeilFix(),   */
30  /* and FT_FloorFix() are declared in freetype.h.                         */
31  /*                                                                       */
32  /*************************************************************************/
33
34
35#include <ft2build.h>
36#include FT_INTERNAL_CALC_H
37#include FT_INTERNAL_DEBUG_H
38#include FT_INTERNAL_OBJECTS_H
39
40
41/* we need to define a 64-bits data type here */
42
43#ifdef FT_LONG64
44
45  typedef FT_INT64  FT_Int64;
46
47#else
48
49  typedef struct  FT_Int64_
50  {
51    FT_UInt32  lo;
52    FT_UInt32  hi;
53
54  } FT_Int64;
55
56#endif /* FT_LONG64 */
57
58
59  /*************************************************************************/
60  /*                                                                       */
61  /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
62  /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
63  /* messages during execution.                                            */
64  /*                                                                       */
65#undef  FT_COMPONENT
66#define FT_COMPONENT  trace_calc
67
68
69  /* The following three functions are available regardless of whether */
70  /* FT_LONG64 is defined.                                             */
71
72  /* documentation is in freetype.h */
73
74  FT_EXPORT_DEF( FT_Fixed )
75  FT_RoundFix( FT_Fixed  a )
76  {
77    return ( a >= 0 ) ?   ( a + 0x8000L ) & ~0xFFFFL
78                      : -((-a + 0x8000L ) & ~0xFFFFL );
79  }
80
81
82  /* documentation is in freetype.h */
83
84  FT_EXPORT_DEF( FT_Fixed )
85  FT_CeilFix( FT_Fixed  a )
86  {
87    return ( a >= 0 ) ?   ( a + 0xFFFFL ) & ~0xFFFFL
88                      : -((-a + 0xFFFFL ) & ~0xFFFFL );
89  }
90
91
92  /* documentation is in freetype.h */
93
94  FT_EXPORT_DEF( FT_Fixed )
95  FT_FloorFix( FT_Fixed  a )
96  {
97    return ( a >= 0 ) ?   a & ~0xFFFFL
98                      : -((-a) & ~0xFFFFL );
99  }
100
101
102  /* documentation is in ftcalc.h */
103
104  FT_EXPORT_DEF( FT_Int32 )
105  FT_Sqrt32( FT_Int32  x )
106  {
107    FT_ULong  val, root, newroot, mask;
108
109
110    root = 0;
111    mask = 0x40000000L;
112    val  = (FT_ULong)x;
113
114    do
115    {
116      newroot = root + mask;
117      if ( newroot <= val )
118      {
119        val -= newroot;
120        root = newroot + mask;
121      }
122
123      root >>= 1;
124      mask >>= 2;
125
126    } while ( mask != 0 );
127
128    return root;
129  }
130
131
132#ifdef FT_LONG64
133
134
135  /* documentation is in freetype.h */
136
137  FT_EXPORT_DEF( FT_Long )
138  FT_MulDiv( FT_Long  a,
139             FT_Long  b,
140             FT_Long  c )
141  {
142    FT_Int   s;
143    FT_Long  d;
144
145
146    s = 1;
147    if ( a < 0 ) { a = -a; s = -1; }
148    if ( b < 0 ) { b = -b; s = -s; }
149    if ( c < 0 ) { c = -c; s = -s; }
150
151    d = (FT_Long)( c > 0 ? ( (FT_Int64)a * b + ( c >> 1 ) ) / c
152                         : 0x7FFFFFFFL );
153
154    return ( s > 0 ) ? d : -d;
155  }
156
157
158#ifdef TT_CONFIG_OPTION_BYTECODE_INTERPRETER
159
160  /* documentation is in ftcalc.h */
161
162  FT_BASE_DEF( FT_Long )
163  FT_MulDiv_No_Round( FT_Long  a,
164                      FT_Long  b,
165                      FT_Long  c )
166  {
167    FT_Int   s;
168    FT_Long  d;
169
170
171    s = 1;
172    if ( a < 0 ) { a = -a; s = -1; }
173    if ( b < 0 ) { b = -b; s = -s; }
174    if ( c < 0 ) { c = -c; s = -s; }
175
176    d = (FT_Long)( c > 0 ? (FT_Int64)a * b / c
177                         : 0x7FFFFFFFL );
178
179    return ( s > 0 ) ? d : -d;
180  }
181
182#endif /* TT_CONFIG_OPTION_BYTECODE_INTERPRETER */
183
184
185  /* documentation is in freetype.h */
186
187  FT_EXPORT_DEF( FT_Long )
188  FT_MulFix( FT_Long  a,
189             FT_Long  b )
190  {
191    FT_Int   s = 1;
192    FT_Long  c;
193
194
195    if ( a < 0 ) { a = -a; s = -1; }
196    if ( b < 0 ) { b = -b; s = -s; }
197
198    c = (FT_Long)( ( (FT_Int64)a * b + 0x8000L ) >> 16 );
199    return ( s > 0 ) ? c : -c ;
200  }
201
202
203  /* documentation is in freetype.h */
204
205  FT_EXPORT_DEF( FT_Long )
206  FT_DivFix( FT_Long  a,
207             FT_Long  b )
208  {
209    FT_Int32   s;
210    FT_UInt32  q;
211
212    s = 1;
213    if ( a < 0 ) { a = -a; s = -1; }
214    if ( b < 0 ) { b = -b; s = -s; }
215
216    if ( b == 0 )
217      /* check for division by 0 */
218      q = 0x7FFFFFFFL;
219    else
220      /* compute result directly */
221      q = (FT_UInt32)( ( ( (FT_Int64)a << 16 ) + ( b >> 1 ) ) / b );
222
223    return ( s < 0 ? -(FT_Long)q : (FT_Long)q );
224  }
225
226
227#else /* FT_LONG64 */
228
229
230  static void
231  ft_multo64( FT_UInt32  x,
232              FT_UInt32  y,
233              FT_Int64  *z )
234  {
235    FT_UInt32  lo1, hi1, lo2, hi2, lo, hi, i1, i2;
236
237
238    lo1 = x & 0x0000FFFFU;  hi1 = x >> 16;
239    lo2 = y & 0x0000FFFFU;  hi2 = y >> 16;
240
241    lo = lo1 * lo2;
242    i1 = lo1 * hi2;
243    i2 = lo2 * hi1;
244    hi = hi1 * hi2;
245
246    /* Check carry overflow of i1 + i2 */
247    i1 += i2;
248    hi += (FT_UInt32)( i1 < i2 ) << 16;
249
250    hi += i1 >> 16;
251    i1  = i1 << 16;
252
253    /* Check carry overflow of i1 + lo */
254    lo += i1;
255    hi += ( lo < i1 );
256
257    z->lo = lo;
258    z->hi = hi;
259  }
260
261
262  static FT_UInt32
263  ft_div64by32( FT_UInt32  hi,
264                FT_UInt32  lo,
265                FT_UInt32  y )
266  {
267    FT_UInt32  r, q;
268    FT_Int     i;
269
270
271    q = 0;
272    r = hi;
273
274    if ( r >= y )
275      return (FT_UInt32)0x7FFFFFFFL;
276
277    i = 32;
278    do
279    {
280      r <<= 1;
281      q <<= 1;
282      r  |= lo >> 31;
283
284      if ( r >= (FT_UInt32)y )
285      {
286        r -= y;
287        q |= 1;
288      }
289      lo <<= 1;
290    } while ( --i );
291
292    return q;
293  }
294
295
296  /* documentation is in ftcalc.h */
297
298  FT_EXPORT_DEF( void )
299  FT_Add64( FT_Int64*  x,
300            FT_Int64*  y,
301            FT_Int64  *z )
302  {
303    register FT_UInt32  lo, hi, max;
304
305
306    max = x->lo > y->lo ? x->lo : y->lo;
307    lo  = x->lo + y->lo;
308    hi  = x->hi + y->hi + ( lo < max );
309
310    z->lo = lo;
311    z->hi = hi;
312  }
313
314
315  /* documentation is in freetype.h */
316
317  FT_EXPORT_DEF( FT_Long )
318  FT_MulDiv( FT_Long  a,
319             FT_Long  b,
320             FT_Long  c )
321  {
322    long  s;
323
324
325    if ( a == 0 || b == c )
326      return a;
327
328    s  = a; a = FT_ABS( a );
329    s ^= b; b = FT_ABS( b );
330    s ^= c; c = FT_ABS( c );
331
332    if ( a <= 46340L && b <= 46340L && c <= 176095L && c > 0 )
333      a = ( a * b + ( c >> 1 ) ) / c;
334
335    else if ( c > 0 )
336    {
337      FT_Int64  temp, temp2;
338
339
340      ft_multo64( a, b, &temp );
341
342      temp2.hi = 0;
343      temp2.lo = (FT_UInt32)(c >> 1);
344      FT_Add64( &temp, &temp2, &temp );
345      a = ft_div64by32( temp.hi, temp.lo, c );
346    }
347    else
348      a = 0x7FFFFFFFL;
349
350    return ( s < 0 ? -a : a );
351  }
352
353
354#ifdef TT_CONFIG_OPTION_BYTECODE_INTERPRETER
355
356  FT_BASE_DEF( FT_Long )
357  FT_MulDiv_No_Round( FT_Long  a,
358                      FT_Long  b,
359                      FT_Long  c )
360  {
361    long  s;
362
363
364    if ( a == 0 || b == c )
365      return a;
366
367    s  = a; a = FT_ABS( a );
368    s ^= b; b = FT_ABS( b );
369    s ^= c; c = FT_ABS( c );
370
371    if ( a <= 46340L && b <= 46340L && c > 0 )
372      a = a * b / c;
373
374    else if ( c > 0 )
375    {
376      FT_Int64  temp;
377
378
379      ft_multo64( a, b, &temp );
380      a = ft_div64by32( temp.hi, temp.lo, c );
381    }
382    else
383      a = 0x7FFFFFFFL;
384
385    return ( s < 0 ? -a : a );
386  }
387
388#endif /* TT_CONFIG_OPTION_BYTECODE_INTERPRETER */
389
390
391  /* documentation is in freetype.h */
392
393  FT_EXPORT_DEF( FT_Long )
394  FT_MulFix( FT_Long  a,
395             FT_Long  b )
396  {
397    FT_Long   s;
398    FT_ULong  ua, ub;
399
400
401    if ( a == 0 || b == 0x10000L )
402      return a;
403
404    s  = a; a = FT_ABS(a);
405    s ^= b; b = FT_ABS(b);
406
407    ua = (FT_ULong)a;
408    ub = (FT_ULong)b;
409
410    if ( ua <= 2048 && ub <= 1048576L )
411    {
412      ua = ( ua * ub + 0x8000L ) >> 16;
413    }
414    else
415    {
416      FT_ULong  al = ua & 0xFFFFL;
417
418
419      ua = ( ua >> 16 ) * ub +  al * ( ub >> 16 ) +
420           ( ( al * ( ub & 0xFFFFL ) + 0x8000L ) >> 16 );
421    }
422
423    return ( s < 0 ? -(FT_Long)ua : (FT_Long)ua );
424  }
425
426
427  /* documentation is in freetype.h */
428
429  FT_EXPORT_DEF( FT_Long )
430  FT_DivFix( FT_Long  a,
431             FT_Long  b )
432  {
433    FT_Int32   s;
434    FT_UInt32  q;
435
436
437    s  = a; a = FT_ABS(a);
438    s ^= b; b = FT_ABS(b);
439
440    if ( b == 0 )
441    {
442      /* check for division by 0 */
443      q = 0x7FFFFFFFL;
444    }
445    else if ( ( a >> 16 ) == 0 )
446    {
447      /* compute result directly */
448      q = (FT_UInt32)( (a << 16) + (b >> 1) ) / (FT_UInt32)b;
449    }
450    else
451    {
452      /* we need more bits; we have to do it by hand */
453      FT_Int64  temp, temp2;
454
455      temp.hi  = (FT_Int32) (a >> 16);
456      temp.lo  = (FT_UInt32)(a << 16);
457      temp2.hi = 0;
458      temp2.lo = (FT_UInt32)( b >> 1 );
459      FT_Add64( &temp, &temp2, &temp );
460      q = ft_div64by32( temp.hi, temp.lo, b );
461    }
462
463    return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
464  }
465
466
467  /* documentation is in ftcalc.h */
468
469  FT_EXPORT_DEF( void )
470  FT_MulTo64( FT_Int32   x,
471              FT_Int32   y,
472              FT_Int64  *z )
473  {
474    FT_Int32  s;
475
476
477    s  = x; x = FT_ABS( x );
478    s ^= y; y = FT_ABS( y );
479
480    ft_multo64( x, y, z );
481
482    if ( s < 0 )
483    {
484      z->lo = (FT_UInt32)-(FT_Int32)z->lo;
485      z->hi = ~z->hi + !( z->lo );
486    }
487  }
488
489
490  /* documentation is in ftcalc.h */
491
492  /* apparently, the second version of this code is not compiled correctly */
493  /* on Mac machines with the MPW C compiler..  tsss, tsss, tss...         */
494
495#if 1
496
497  FT_EXPORT_DEF( FT_Int32 )
498  FT_Div64by32( FT_Int64*  x,
499                FT_Int32   y )
500  {
501    FT_Int32   s;
502    FT_UInt32  q, r, i, lo;
503
504
505    s  = x->hi;
506    if ( s < 0 )
507    {
508      x->lo = (FT_UInt32)-(FT_Int32)x->lo;
509      x->hi = ~x->hi + !x->lo;
510    }
511    s ^= y;  y = FT_ABS( y );
512
513    /* Shortcut */
514    if ( x->hi == 0 )
515    {
516      if ( y > 0 )
517        q = x->lo / y;
518      else
519        q = 0x7FFFFFFFL;
520
521      return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
522    }
523
524    r  = x->hi;
525    lo = x->lo;
526
527    if ( r >= (FT_UInt32)y ) /* we know y is to be treated as unsigned here */
528      return ( s < 0 ? 0x80000001UL : 0x7FFFFFFFUL );
529                             /* Return Max/Min Int32 if division overflow. */
530                             /* This includes division by zero! */
531    q = 0;
532    for ( i = 0; i < 32; i++ )
533    {
534      r <<= 1;
535      q <<= 1;
536      r  |= lo >> 31;
537
538      if ( r >= (FT_UInt32)y )
539      {
540        r -= y;
541        q |= 1;
542      }
543      lo <<= 1;
544    }
545
546    return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
547  }
548
549#else /* 0 */
550
551  FT_EXPORT_DEF( FT_Int32 )
552  FT_Div64by32( FT_Int64*  x,
553                FT_Int32   y )
554  {
555    FT_Int32   s;
556    FT_UInt32  q;
557
558
559    s  = x->hi;
560    if ( s < 0 )
561    {
562      x->lo = (FT_UInt32)-(FT_Int32)x->lo;
563      x->hi = ~x->hi + !x->lo;
564    }
565    s ^= y;  y = FT_ABS( y );
566
567    /* Shortcut */
568    if ( x->hi == 0 )
569    {
570      if ( y > 0 )
571        q = ( x->lo + ( y >> 1 ) ) / y;
572      else
573        q = 0x7FFFFFFFL;
574
575      return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
576    }
577
578    q = ft_div64by32( x->hi, x->lo, y );
579
580    return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
581  }
582
583#endif /* 0 */
584
585
586#endif /* FT_LONG64 */
587
588
589  /* documentation is in ftcalc.h */
590
591  FT_EXPORT_DEF( FT_Int32 )
592  FT_SqrtFixed( FT_Int32  x )
593  {
594    FT_UInt32  root, rem_hi, rem_lo, test_div;
595    FT_Int     count;
596
597
598    root = 0;
599
600    if ( x > 0 )
601    {
602      rem_hi = 0;
603      rem_lo = x;
604      count  = 24;
605      do
606      {
607        rem_hi   = ( rem_hi << 2 ) | ( rem_lo >> 30 );
608        rem_lo <<= 2;
609        root   <<= 1;
610        test_div = ( root << 1 ) + 1;
611
612        if ( rem_hi >= test_div )
613        {
614          rem_hi -= test_div;
615          root   += 1;
616        }
617      } while ( --count );
618    }
619
620    return (FT_Int32)root;
621  }
622
623
624/* END */
Note: See TracBrowser for help on using the repository browser.