Ryo Hagimoto / zbar_010

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

Dependents:   GR-PEACH_Camera_in_barcode levkov_ov7670

zbar/qrcode/util.c@1:500d42699c34, 2016-04-19 (annotated)

Committer:
RyoheiHagimoto
Date:
Tue Apr 19 02:19:39 2016 +0000
Revision:
1:500d42699c34
Parent:
0:56c5742b9e2b 
Add copying.txt and license.txt

Who changed what in which revision?

UserRevisionLine numberNew contents of line
RyoheiHagimoto 0:56c5742b9e2b 1 /*Copyright (C) 2008-2009 Timothy B. Terriberry (tterribe@xiph.org)
RyoheiHagimoto 0:56c5742b9e2b 2 You can redistribute this library and/or modify it under the terms of the
RyoheiHagimoto 0:56c5742b9e2b 3 GNU Lesser General Public License as published by the Free Software
RyoheiHagimoto 0:56c5742b9e2b 4 Foundation; either version 2.1 of the License, or (at your option) any later
RyoheiHagimoto 0:56c5742b9e2b 5 version.*/
RyoheiHagimoto 0:56c5742b9e2b 6 #include <stdlib.h>
RyoheiHagimoto 0:56c5742b9e2b 7 #include "util.h"
RyoheiHagimoto 0:56c5742b9e2b 8
RyoheiHagimoto 0:56c5742b9e2b 9 /*Computes floor(sqrt(_val)) exactly.*/
RyoheiHagimoto 0:56c5742b9e2b 10 unsigned qr_isqrt(unsigned _val){
RyoheiHagimoto 0:56c5742b9e2b 11 unsigned g;
RyoheiHagimoto 0:56c5742b9e2b 12 unsigned b;
RyoheiHagimoto 0:56c5742b9e2b 13 int bshift;
RyoheiHagimoto 0:56c5742b9e2b 14 /*Uses the second method from
RyoheiHagimoto 0:56c5742b9e2b 15 http://www.azillionmonkeys.com/qed/sqroot.html
RyoheiHagimoto 0:56c5742b9e2b 16 The main idea is to search for the largest binary digit b such that
RyoheiHagimoto 0:56c5742b9e2b 17 (g+b)*(g+b) <= _val, and add it to the solution g.*/
RyoheiHagimoto 0:56c5742b9e2b 18 g=0;
RyoheiHagimoto 0:56c5742b9e2b 19 b=0x8000;
RyoheiHagimoto 0:56c5742b9e2b 20 for(bshift=16;bshift-->0;){
RyoheiHagimoto 0:56c5742b9e2b 21 unsigned t;
RyoheiHagimoto 0:56c5742b9e2b 22 t=(g<<1)+b<<bshift;
RyoheiHagimoto 0:56c5742b9e2b 23 if(t<=_val){
RyoheiHagimoto 0:56c5742b9e2b 24 g+=b;
RyoheiHagimoto 0:56c5742b9e2b 25 _val-=t;
RyoheiHagimoto 0:56c5742b9e2b 26 }
RyoheiHagimoto 0:56c5742b9e2b 27 b>>=1;
RyoheiHagimoto 0:56c5742b9e2b 28 }
RyoheiHagimoto 0:56c5742b9e2b 29 return g;
RyoheiHagimoto 0:56c5742b9e2b 30 }
RyoheiHagimoto 0:56c5742b9e2b 31
RyoheiHagimoto 0:56c5742b9e2b 32 /*Computes sqrt(_x*_x+_y*_y) using CORDIC.
RyoheiHagimoto 0:56c5742b9e2b 33 This implementation is valid for all 32-bit inputs and returns a result
RyoheiHagimoto 0:56c5742b9e2b 34 accurate to about 27 bits of precision.
RyoheiHagimoto 0:56c5742b9e2b 35 It has been tested for all postiive 16-bit inputs, where it returns correctly
RyoheiHagimoto 0:56c5742b9e2b 36 rounded results in 99.998% of cases and the maximum error is
RyoheiHagimoto 0:56c5742b9e2b 37 0.500137134862598032 (for _x=48140, _y=63018).
RyoheiHagimoto 0:56c5742b9e2b 38 Very nearly all results less than (1<<16) are correctly rounded.
RyoheiHagimoto 0:56c5742b9e2b 39 All Pythagorean triples with a hypotenuse of less than ((1<<27)-1) evaluate
RyoheiHagimoto 0:56c5742b9e2b 40 correctly, and the total bias over all Pythagorean triples is -0.04579, with
RyoheiHagimoto 0:56c5742b9e2b 41 a relative RMS error of 7.2864E-10 and a relative peak error of 7.4387E-9.*/
RyoheiHagimoto 0:56c5742b9e2b 42 unsigned qr_ihypot(int _x,int _y){
RyoheiHagimoto 0:56c5742b9e2b 43 unsigned x;
RyoheiHagimoto 0:56c5742b9e2b 44 unsigned y;
RyoheiHagimoto 0:56c5742b9e2b 45 int mask;
RyoheiHagimoto 0:56c5742b9e2b 46 int shift;
RyoheiHagimoto 0:56c5742b9e2b 47 int u;
RyoheiHagimoto 0:56c5742b9e2b 48 int v;
RyoheiHagimoto 0:56c5742b9e2b 49 int i;
RyoheiHagimoto 0:56c5742b9e2b 50 x=_x=abs(_x);
RyoheiHagimoto 0:56c5742b9e2b 51 y=_y=abs(_y);
RyoheiHagimoto 0:56c5742b9e2b 52 mask=-(x>y)&(_x^_y);
RyoheiHagimoto 0:56c5742b9e2b 53 x^=mask;
RyoheiHagimoto 0:56c5742b9e2b 54 y^=mask;
RyoheiHagimoto 0:56c5742b9e2b 55 _y^=mask;
RyoheiHagimoto 0:56c5742b9e2b 56 shift=31-qr_ilog(y);
RyoheiHagimoto 0:56c5742b9e2b 57 shift=QR_MAXI(shift,0);
RyoheiHagimoto 0:56c5742b9e2b 58 x=(unsigned)((x<<shift)*0x9B74EDAAULL>>32);
RyoheiHagimoto 0:56c5742b9e2b 59 _y=(int)((_y<<shift)*0x9B74EDA9LL>>32);
RyoheiHagimoto 0:56c5742b9e2b 60 u=x;
RyoheiHagimoto 0:56c5742b9e2b 61 mask=-(_y<0);
RyoheiHagimoto 0:56c5742b9e2b 62 x+=_y+mask^mask;
RyoheiHagimoto 0:56c5742b9e2b 63 _y-=u+mask^mask;
RyoheiHagimoto 0:56c5742b9e2b 64 u=x+1>>1;
RyoheiHagimoto 0:56c5742b9e2b 65 v=_y+1>>1;
RyoheiHagimoto 0:56c5742b9e2b 66 mask=-(_y<0);
RyoheiHagimoto 0:56c5742b9e2b 67 x+=v+mask^mask;
RyoheiHagimoto 0:56c5742b9e2b 68 _y-=u+mask^mask;
RyoheiHagimoto 0:56c5742b9e2b 69 for(i=1;i<16;i++){
RyoheiHagimoto 0:56c5742b9e2b 70 int r;
RyoheiHagimoto 0:56c5742b9e2b 71 u=x+1>>2;
RyoheiHagimoto 0:56c5742b9e2b 72 r=(1<<2*i)>>1;
RyoheiHagimoto 0:56c5742b9e2b 73 v=_y+r>>2*i;
RyoheiHagimoto 0:56c5742b9e2b 74 mask=-(_y<0);
RyoheiHagimoto 0:56c5742b9e2b 75 x+=v+mask^mask;
RyoheiHagimoto 0:56c5742b9e2b 76 _y=_y-(u+mask^mask)<<1;
RyoheiHagimoto 0:56c5742b9e2b 77 }
RyoheiHagimoto 0:56c5742b9e2b 78 return x+((1U<<shift)>>1)>>shift;
RyoheiHagimoto 0:56c5742b9e2b 79 }
RyoheiHagimoto 0:56c5742b9e2b 80
RyoheiHagimoto 0:56c5742b9e2b 81 #if defined(__GNUC__) && defined(HAVE_FEATURES_H)
RyoheiHagimoto 0:56c5742b9e2b 82 # include <features.h>
RyoheiHagimoto 0:56c5742b9e2b 83 # if __GNUC_PREREQ(3,4)
RyoheiHagimoto 0:56c5742b9e2b 84 # include <limits.h>
RyoheiHagimoto 0:56c5742b9e2b 85 # if INT_MAX>=2147483647
RyoheiHagimoto 0:56c5742b9e2b 86 # define QR_CLZ0 sizeof(unsigned)*CHAR_BIT
RyoheiHagimoto 0:56c5742b9e2b 87 # define QR_CLZ(_x) (__builtin_clz(_x))
RyoheiHagimoto 0:56c5742b9e2b 88 # elif LONG_MAX>=2147483647L
RyoheiHagimoto 0:56c5742b9e2b 89 # define QR_CLZ0 sizeof(unsigned long)*CHAR_BIT
RyoheiHagimoto 0:56c5742b9e2b 90 # define QR_CLZ(_x) (__builtin_clzl(_x))
RyoheiHagimoto 0:56c5742b9e2b 91 # endif
RyoheiHagimoto 0:56c5742b9e2b 92 # endif
RyoheiHagimoto 0:56c5742b9e2b 93 #endif
RyoheiHagimoto 0:56c5742b9e2b 94
RyoheiHagimoto 0:56c5742b9e2b 95 int qr_ilog(unsigned _v){
RyoheiHagimoto 0:56c5742b9e2b 96 #if defined(QR_CLZ)
RyoheiHagimoto 0:56c5742b9e2b 97 /*Note that __builtin_clz is not defined when _x==0, according to the gcc
RyoheiHagimoto 0:56c5742b9e2b 98 documentation (and that of the x86 BSR instruction that implements it), so
RyoheiHagimoto 0:56c5742b9e2b 99 we have to special-case it.*/
RyoheiHagimoto 0:56c5742b9e2b 100 return QR_CLZ0-QR_CLZ(_v)&-!!_v;
RyoheiHagimoto 0:56c5742b9e2b 101 #else
RyoheiHagimoto 0:56c5742b9e2b 102 int ret;
RyoheiHagimoto 0:56c5742b9e2b 103 int m;
RyoheiHagimoto 0:56c5742b9e2b 104 m=!!(_v&0xFFFF0000)<<4;
RyoheiHagimoto 0:56c5742b9e2b 105 _v>>=m;
RyoheiHagimoto 0:56c5742b9e2b 106 ret=m;
RyoheiHagimoto 0:56c5742b9e2b 107 m=!!(_v&0xFF00)<<3;
RyoheiHagimoto 0:56c5742b9e2b 108 _v>>=m;
RyoheiHagimoto 0:56c5742b9e2b 109 ret|=m;
RyoheiHagimoto 0:56c5742b9e2b 110 m=!!(_v&0xF0)<<2;
RyoheiHagimoto 0:56c5742b9e2b 111 _v>>=m;
RyoheiHagimoto 0:56c5742b9e2b 112 ret|=m;
RyoheiHagimoto 0:56c5742b9e2b 113 m=!!(_v&0xC)<<1;
RyoheiHagimoto 0:56c5742b9e2b 114 _v>>=m;
RyoheiHagimoto 0:56c5742b9e2b 115 ret|=m;
RyoheiHagimoto 0:56c5742b9e2b 116 ret|=!!(_v&0x2);
RyoheiHagimoto 0:56c5742b9e2b 117 return ret + !!_v;
RyoheiHagimoto 0:56c5742b9e2b 118 #endif
RyoheiHagimoto 0:56c5742b9e2b 119 }
RyoheiHagimoto 0:56c5742b9e2b 120
RyoheiHagimoto 0:56c5742b9e2b 121 #if defined(QR_TEST_SQRT)
RyoheiHagimoto 0:56c5742b9e2b 122 #include <math.h>
RyoheiHagimoto 0:56c5742b9e2b 123 #include <stdio.h>
RyoheiHagimoto 0:56c5742b9e2b 124
RyoheiHagimoto 0:56c5742b9e2b 125 /*Exhaustively test the integer square root function.*/
RyoheiHagimoto 0:56c5742b9e2b 126 int main(void){
RyoheiHagimoto 0:56c5742b9e2b 127 unsigned u;
RyoheiHagimoto 0:56c5742b9e2b 128 u=0;
RyoheiHagimoto 0:56c5742b9e2b 129 do{
RyoheiHagimoto 0:56c5742b9e2b 130 unsigned r;
RyoheiHagimoto 0:56c5742b9e2b 131 unsigned s;
RyoheiHagimoto 0:56c5742b9e2b 132 r=qr_isqrt(u);
RyoheiHagimoto 0:56c5742b9e2b 133 s=(int)sqrt(u);
RyoheiHagimoto 0:56c5742b9e2b 134 if(r!=s)printf("%u: %u!=%u\n",u,r,s);
RyoheiHagimoto 0:56c5742b9e2b 135 u++;
RyoheiHagimoto 0:56c5742b9e2b 136 }
RyoheiHagimoto 0:56c5742b9e2b 137 while(u);
RyoheiHagimoto 0:56c5742b9e2b 138 return 0;
RyoheiHagimoto 0:56c5742b9e2b 139 }
RyoheiHagimoto 0:56c5742b9e2b 140 #endif
RyoheiHagimoto 0:56c5742b9e2b 141