ZBar bar code reader . http://zbar.sourceforge.net/ ZBar is licensed under the GNU LGPL 2.1 to enable development of both open source and commercial projects.

Dependents:   GR-PEACH_Camera_in_barcode levkov_ov7670

Embed: (wiki syntax)

« Back to documentation index

Show/hide line numbers util.c Source File

util.c

00001 /*Copyright (C) 2008-2009  Timothy B. Terriberry (tterribe@xiph.org)
00002   You can redistribute this library and/or modify it under the terms of the
00003    GNU Lesser General Public License as published by the Free Software
00004    Foundation; either version 2.1 of the License, or (at your option) any later
00005    version.*/
00006 #include <stdlib.h>
00007 #include "util.h"
00008 
00009 /*Computes floor(sqrt(_val)) exactly.*/
00010 unsigned qr_isqrt(unsigned _val){
00011   unsigned g;
00012   unsigned b;
00013   int      bshift;
00014   /*Uses the second method from
00015      http://www.azillionmonkeys.com/qed/sqroot.html
00016     The main idea is to search for the largest binary digit b such that
00017      (g+b)*(g+b) <= _val, and add it to the solution g.*/
00018   g=0;
00019   b=0x8000;
00020   for(bshift=16;bshift-->0;){
00021     unsigned t;
00022     t=(g<<1)+b<<bshift;
00023     if(t<=_val){
00024       g+=b;
00025       _val-=t;
00026     }
00027     b>>=1;
00028   }
00029   return g;
00030 }
00031 
00032 /*Computes sqrt(_x*_x+_y*_y) using CORDIC.
00033   This implementation is valid for all 32-bit inputs and returns a result
00034    accurate to about 27 bits of precision.
00035   It has been tested for all postiive 16-bit inputs, where it returns correctly
00036    rounded results in 99.998% of cases and the maximum error is
00037    0.500137134862598032 (for _x=48140, _y=63018).
00038   Very nearly all results less than (1<<16) are correctly rounded.
00039   All Pythagorean triples with a hypotenuse of less than ((1<<27)-1) evaluate
00040    correctly, and the total bias over all Pythagorean triples is -0.04579, with
00041    a relative RMS error of 7.2864E-10 and a relative peak error of 7.4387E-9.*/
00042 unsigned qr_ihypot(int _x,int _y){
00043   unsigned x;
00044   unsigned y;
00045   int      mask;
00046   int      shift;
00047   int      u;
00048   int      v;
00049   int      i;
00050   x=_x=abs(_x);
00051   y=_y=abs(_y);
00052   mask=-(x>y)&(_x^_y);
00053   x^=mask;
00054   y^=mask;
00055   _y^=mask;
00056   shift=31-qr_ilog(y);
00057   shift=QR_MAXI(shift,0);
00058   x=(unsigned)((x<<shift)*0x9B74EDAAULL>>32);
00059   _y=(int)((_y<<shift)*0x9B74EDA9LL>>32);
00060   u=x;
00061   mask=-(_y<0);
00062   x+=_y+mask^mask;
00063   _y-=u+mask^mask;
00064   u=x+1>>1;
00065   v=_y+1>>1;
00066   mask=-(_y<0);
00067   x+=v+mask^mask;
00068   _y-=u+mask^mask;
00069   for(i=1;i<16;i++){
00070     int r;
00071     u=x+1>>2;
00072     r=(1<<2*i)>>1;
00073     v=_y+r>>2*i;
00074     mask=-(_y<0);
00075     x+=v+mask^mask;
00076     _y=_y-(u+mask^mask)<<1;
00077   }
00078   return x+((1U<<shift)>>1)>>shift;
00079 }
00080 
00081 #if defined(__GNUC__) && defined(HAVE_FEATURES_H)
00082 # include <features.h>
00083 # if __GNUC_PREREQ(3,4)
00084 #  include <limits.h>
00085 #  if INT_MAX>=2147483647
00086 #   define QR_CLZ0 sizeof(unsigned)*CHAR_BIT
00087 #   define QR_CLZ(_x) (__builtin_clz(_x))
00088 #  elif LONG_MAX>=2147483647L
00089 #   define QR_CLZ0 sizeof(unsigned long)*CHAR_BIT
00090 #   define QR_CLZ(_x) (__builtin_clzl(_x))
00091 #  endif
00092 # endif
00093 #endif
00094 
00095 int qr_ilog(unsigned _v){
00096 #if defined(QR_CLZ)
00097 /*Note that __builtin_clz is not defined when _x==0, according to the gcc
00098    documentation (and that of the x86 BSR instruction that implements it), so
00099    we have to special-case it.*/
00100   return QR_CLZ0-QR_CLZ(_v)&-!!_v;
00101 #else
00102   int ret;
00103   int m;
00104   m=!!(_v&0xFFFF0000)<<4;
00105   _v>>=m;
00106   ret=m;
00107   m=!!(_v&0xFF00)<<3;
00108   _v>>=m;
00109   ret|=m;
00110   m=!!(_v&0xF0)<<2;
00111   _v>>=m;
00112   ret|=m;
00113   m=!!(_v&0xC)<<1;
00114   _v>>=m;
00115   ret|=m;
00116   ret|=!!(_v&0x2);
00117   return ret + !!_v;
00118 #endif
00119 }
00120 
00121 #if defined(QR_TEST_SQRT)
00122 #include <math.h>
00123 #include <stdio.h>
00124 
00125 /*Exhaustively test the integer square root function.*/
00126 int main(void){
00127   unsigned u;
00128   u=0;
00129   do{
00130     unsigned r;
00131     unsigned s;
00132     r=qr_isqrt(u);
00133     s=(int)sqrt(u);
00134     if(r!=s)printf("%u: %u!=%u\n",u,r,s);
00135     u++;
00136   }
00137   while(u);
00138   return 0;
00139 }
00140 #endif
00141