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
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
Generated on Tue Jul 12 2022 18:54:12 by 1.7.2