Ryo Hagimoto / zbar_010

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

LICENSE

The ZBar Bar Code Reader is Copyright (C) 2007-2009 Jeff Brown <spadix@users.sourceforge.net> The QR Code reader is Copyright (C) 1999-2009 Timothy B. Terriberry <tterribe@xiph.org>

You can redistribute this library and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

ISAAC is based on the public domain implementation by Robert J. Jenkins Jr., and is itself public domain.

Portions of the bit stream reader are copyright (C) The Xiph.Org Foundation 1994-2008, and are licensed under a BSD-style license.

The Reed-Solomon decoder is derived from an implementation (C) 1991-1995 Henry Minsky (hqm@ua.com, hqm@ai.mit.edu), and is licensed under the LGPL with permission.

zbar/qrcode/bch15_5.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 "bch15_5.h"
RyoheiHagimoto 0:56c5742b9e2b 7
RyoheiHagimoto 0:56c5742b9e2b 8 /*A cycle in GF(2**4) generated by alpha=(x**4+x+1).
RyoheiHagimoto 0:56c5742b9e2b 9 It is extended an extra 16 entries to avoid some expensive mod operations.*/
RyoheiHagimoto 0:56c5742b9e2b 10 static const unsigned char gf16_exp[31]={
RyoheiHagimoto 0:56c5742b9e2b 11 1,2,4,8,3,6,12,11,5,10,7,14,15,13,9,1,2,4,8,3,6,12,11,5,10,7,14,15,13,9,1
RyoheiHagimoto 0:56c5742b9e2b 12 };
RyoheiHagimoto 0:56c5742b9e2b 13
RyoheiHagimoto 0:56c5742b9e2b 14 /*The location of each integer 1...16 in the cycle.*/
RyoheiHagimoto 0:56c5742b9e2b 15 static const signed char gf16_log[16]={
RyoheiHagimoto 0:56c5742b9e2b 16 -1,0,1,4,2,8,5,10,3,14,9,7,6,13,11,12
RyoheiHagimoto 0:56c5742b9e2b 17 };
RyoheiHagimoto 0:56c5742b9e2b 18
RyoheiHagimoto 0:56c5742b9e2b 19 /*Multiplication in GF(2**4) using logarithms.*/
RyoheiHagimoto 0:56c5742b9e2b 20 static unsigned gf16_mul(unsigned _a,unsigned _b){
RyoheiHagimoto 0:56c5742b9e2b 21 return _a==0||_b==0?0:gf16_exp[gf16_log[_a]+gf16_log[_b]];
RyoheiHagimoto 0:56c5742b9e2b 22 }
RyoheiHagimoto 0:56c5742b9e2b 23
RyoheiHagimoto 0:56c5742b9e2b 24 /*Division in GF(2**4) using logarithms.
RyoheiHagimoto 0:56c5742b9e2b 25 The result when dividing by zero is undefined.*/
RyoheiHagimoto 0:56c5742b9e2b 26 static unsigned gf16_div(unsigned _a,unsigned _b){
RyoheiHagimoto 0:56c5742b9e2b 27 return _a==0?0:gf16_exp[gf16_log[_a]+15-gf16_log[_b]];
RyoheiHagimoto 0:56c5742b9e2b 28 }
RyoheiHagimoto 0:56c5742b9e2b 29
RyoheiHagimoto 0:56c5742b9e2b 30 /*Multiplication in GF(2**4) when the second argument is known to be non-zero
RyoheiHagimoto 0:56c5742b9e2b 31 (proven by representing it by its logarithm).*/
RyoheiHagimoto 0:56c5742b9e2b 32 static unsigned gf16_hmul(unsigned _a,unsigned _logb){
RyoheiHagimoto 0:56c5742b9e2b 33 return _a==0?0:gf16_exp[gf16_log[_a]+_logb];
RyoheiHagimoto 0:56c5742b9e2b 34 }
RyoheiHagimoto 0:56c5742b9e2b 35
RyoheiHagimoto 0:56c5742b9e2b 36 /*The syndrome normally has five values, S_1 ... S_5.
RyoheiHagimoto 0:56c5742b9e2b 37 We only calculate and store the odd ones in _s, since S_2=S_1**2 and
RyoheiHagimoto 0:56c5742b9e2b 38 S_4=S_2**2.
RyoheiHagimoto 0:56c5742b9e2b 39 Returns zero iff all the syndrome values are zero.*/
RyoheiHagimoto 0:56c5742b9e2b 40 static int bch15_5_calc_syndrome(unsigned _s[3],unsigned _y){
RyoheiHagimoto 0:56c5742b9e2b 41 unsigned p;
RyoheiHagimoto 0:56c5742b9e2b 42 int i;
RyoheiHagimoto 0:56c5742b9e2b 43 int j;
RyoheiHagimoto 0:56c5742b9e2b 44 p=0;
RyoheiHagimoto 0:56c5742b9e2b 45 for(i=0;i<15;i++)if(_y&1<<i)p^=gf16_exp[i];
RyoheiHagimoto 0:56c5742b9e2b 46 _s[0]=p;
RyoheiHagimoto 0:56c5742b9e2b 47 p=0;
RyoheiHagimoto 0:56c5742b9e2b 48 for(i=0;i<3;i++)for(j=0;j<5;j++)if(_y&1<<5*i+j)p^=gf16_exp[j*3];
RyoheiHagimoto 0:56c5742b9e2b 49 _s[1]=p;
RyoheiHagimoto 0:56c5742b9e2b 50 p=0;
RyoheiHagimoto 0:56c5742b9e2b 51 for(i=0;i<5;i++)for(j=0;j<3;j++)if(_y&1<<3*i+j)p^=gf16_exp[j*5];
RyoheiHagimoto 0:56c5742b9e2b 52 _s[2]=p;
RyoheiHagimoto 0:56c5742b9e2b 53 return _s[0]!=0||_s[1]!=0||_s[2]!=0;
RyoheiHagimoto 0:56c5742b9e2b 54 }
RyoheiHagimoto 0:56c5742b9e2b 55
RyoheiHagimoto 0:56c5742b9e2b 56 /*Compute the coefficients of the error-locator polynomial.
RyoheiHagimoto 0:56c5742b9e2b 57 Returns the number of errors (the degree of the polynomial).*/
RyoheiHagimoto 0:56c5742b9e2b 58 static int bch15_5_calc_omega(unsigned _o[3],unsigned _s[3]){
RyoheiHagimoto 0:56c5742b9e2b 59 unsigned s02;
RyoheiHagimoto 0:56c5742b9e2b 60 unsigned tt;
RyoheiHagimoto 0:56c5742b9e2b 61 unsigned dd;
RyoheiHagimoto 0:56c5742b9e2b 62 int d;
RyoheiHagimoto 0:56c5742b9e2b 63 _o[0]=_s[0];
RyoheiHagimoto 0:56c5742b9e2b 64 s02=gf16_mul(_s[0],_s[0]);
RyoheiHagimoto 0:56c5742b9e2b 65 dd=_s[1]^gf16_mul(_s[0],s02);
RyoheiHagimoto 0:56c5742b9e2b 66 tt=_s[2]^gf16_mul(s02,_s[1]);
RyoheiHagimoto 0:56c5742b9e2b 67 _o[1]=dd?gf16_div(tt,dd):0;
RyoheiHagimoto 0:56c5742b9e2b 68 _o[2]=dd^gf16_mul(_s[0],_o[1]);
RyoheiHagimoto 0:56c5742b9e2b 69 for(d=3;d>0&&!_o[d-1];d--);
RyoheiHagimoto 0:56c5742b9e2b 70 return d;
RyoheiHagimoto 0:56c5742b9e2b 71 }
RyoheiHagimoto 0:56c5742b9e2b 72
RyoheiHagimoto 0:56c5742b9e2b 73 /*Find the roots of the error polynomial.
RyoheiHagimoto 0:56c5742b9e2b 74 Returns the number of roots found, or a negative value if the polynomial did
RyoheiHagimoto 0:56c5742b9e2b 75 not have enough roots, indicating a decoding error.*/
RyoheiHagimoto 0:56c5742b9e2b 76 static int bch15_5_calc_epos(unsigned _epos[3],unsigned _s[3]){
RyoheiHagimoto 0:56c5742b9e2b 77 unsigned o[3];
RyoheiHagimoto 0:56c5742b9e2b 78 int nerrors;
RyoheiHagimoto 0:56c5742b9e2b 79 int d;
RyoheiHagimoto 0:56c5742b9e2b 80 int i;
RyoheiHagimoto 0:56c5742b9e2b 81 d=bch15_5_calc_omega(o,_s);
RyoheiHagimoto 0:56c5742b9e2b 82 nerrors=0;
RyoheiHagimoto 0:56c5742b9e2b 83 if(d==1)_epos[nerrors++]=gf16_log[o[0]];
RyoheiHagimoto 0:56c5742b9e2b 84 else if(d>0){
RyoheiHagimoto 0:56c5742b9e2b 85 for(i=0;i<15;i++){
RyoheiHagimoto 0:56c5742b9e2b 86 int i2;
RyoheiHagimoto 0:56c5742b9e2b 87 i2=gf16_log[gf16_exp[i<<1]];
RyoheiHagimoto 0:56c5742b9e2b 88 if(!(gf16_exp[i+i2]^gf16_hmul(o[0],i2)^gf16_hmul(o[1],i)^o[2])){
RyoheiHagimoto 0:56c5742b9e2b 89 _epos[nerrors++]=i;
RyoheiHagimoto 0:56c5742b9e2b 90 }
RyoheiHagimoto 0:56c5742b9e2b 91 }
RyoheiHagimoto 0:56c5742b9e2b 92 if(nerrors<d)return -1;
RyoheiHagimoto 0:56c5742b9e2b 93 }
RyoheiHagimoto 0:56c5742b9e2b 94 return nerrors;
RyoheiHagimoto 0:56c5742b9e2b 95 }
RyoheiHagimoto 0:56c5742b9e2b 96
RyoheiHagimoto 0:56c5742b9e2b 97 int bch15_5_correct(unsigned *_y){
RyoheiHagimoto 0:56c5742b9e2b 98 unsigned s[3];
RyoheiHagimoto 0:56c5742b9e2b 99 unsigned epos[3];
RyoheiHagimoto 0:56c5742b9e2b 100 unsigned y;
RyoheiHagimoto 0:56c5742b9e2b 101 int nerrors;
RyoheiHagimoto 0:56c5742b9e2b 102 int i;
RyoheiHagimoto 0:56c5742b9e2b 103 y=*_y;
RyoheiHagimoto 0:56c5742b9e2b 104 if(!bch15_5_calc_syndrome(s,y))return 0;
RyoheiHagimoto 0:56c5742b9e2b 105 nerrors=bch15_5_calc_epos(epos,s);
RyoheiHagimoto 0:56c5742b9e2b 106 if(nerrors>0){
RyoheiHagimoto 0:56c5742b9e2b 107 /*If we had a non-zero syndrome value, we should always find at least one
RyoheiHagimoto 0:56c5742b9e2b 108 error location, or we've got a decoding error.*/
RyoheiHagimoto 0:56c5742b9e2b 109 for(i=0;i<nerrors;i++)y^=1<<epos[i];
RyoheiHagimoto 0:56c5742b9e2b 110 /*If there were too many errors, we may not find enough roots to reduce the
RyoheiHagimoto 0:56c5742b9e2b 111 syndrome to zero.
RyoheiHagimoto 0:56c5742b9e2b 112 We could recompute it to check, but it's much faster just to check that
RyoheiHagimoto 0:56c5742b9e2b 113 we have a valid codeword.*/
RyoheiHagimoto 0:56c5742b9e2b 114 if(bch15_5_encode(y>>10)==y){
RyoheiHagimoto 0:56c5742b9e2b 115 /*Decoding succeeded.*/
RyoheiHagimoto 0:56c5742b9e2b 116 *_y=y;
RyoheiHagimoto 0:56c5742b9e2b 117 return nerrors;
RyoheiHagimoto 0:56c5742b9e2b 118 }
RyoheiHagimoto 0:56c5742b9e2b 119 }
RyoheiHagimoto 0:56c5742b9e2b 120 /*Decoding failed due to too many bit errors.*/
RyoheiHagimoto 0:56c5742b9e2b 121 return -1;
RyoheiHagimoto 0:56c5742b9e2b 122 }
RyoheiHagimoto 0:56c5742b9e2b 123
RyoheiHagimoto 0:56c5742b9e2b 124 unsigned bch15_5_encode(unsigned _x){
RyoheiHagimoto 0:56c5742b9e2b 125 return (-(_x&1)&0x0537)^(-(_x>>1&1)&0x0A6E)^(-(_x>>2&1)&0x11EB)^
RyoheiHagimoto 0:56c5742b9e2b 126 (-(_x>>3&1)&0x23D6)^(-(_x>>4&1)&0x429B);
RyoheiHagimoto 0:56c5742b9e2b 127 }
RyoheiHagimoto 0:56c5742b9e2b 128
RyoheiHagimoto 0:56c5742b9e2b 129 #if 0
RyoheiHagimoto 0:56c5742b9e2b 130 #include <stdio.h>
RyoheiHagimoto 0:56c5742b9e2b 131
RyoheiHagimoto 0:56c5742b9e2b 132 static unsigned codes[32];
RyoheiHagimoto 0:56c5742b9e2b 133
RyoheiHagimoto 0:56c5742b9e2b 134 static int hamming(int _a,int _b){
RyoheiHagimoto 0:56c5742b9e2b 135 int d;
RyoheiHagimoto 0:56c5742b9e2b 136 int n;
RyoheiHagimoto 0:56c5742b9e2b 137 d=_a^_b;
RyoheiHagimoto 0:56c5742b9e2b 138 for(n=0;d;n++)d&=d-1;
RyoheiHagimoto 0:56c5742b9e2b 139 return n;
RyoheiHagimoto 0:56c5742b9e2b 140 }
RyoheiHagimoto 0:56c5742b9e2b 141
RyoheiHagimoto 0:56c5742b9e2b 142 static int closest(int _y){
RyoheiHagimoto 0:56c5742b9e2b 143 int min_i;
RyoheiHagimoto 0:56c5742b9e2b 144 int min_d;
RyoheiHagimoto 0:56c5742b9e2b 145 int i;
RyoheiHagimoto 0:56c5742b9e2b 146 int d;
RyoheiHagimoto 0:56c5742b9e2b 147 min_i=0;
RyoheiHagimoto 0:56c5742b9e2b 148 min_d=hamming(_y,codes[0]);
RyoheiHagimoto 0:56c5742b9e2b 149 for(i=1;i<32;i++){
RyoheiHagimoto 0:56c5742b9e2b 150 d=hamming(_y,codes[i]);
RyoheiHagimoto 0:56c5742b9e2b 151 if(d<min_d){
RyoheiHagimoto 0:56c5742b9e2b 152 min_d=d;
RyoheiHagimoto 0:56c5742b9e2b 153 min_i=i;
RyoheiHagimoto 0:56c5742b9e2b 154 }
RyoheiHagimoto 0:56c5742b9e2b 155 }
RyoheiHagimoto 0:56c5742b9e2b 156 return codes[min_i];
RyoheiHagimoto 0:56c5742b9e2b 157 }
RyoheiHagimoto 0:56c5742b9e2b 158
RyoheiHagimoto 0:56c5742b9e2b 159 int main(void){
RyoheiHagimoto 0:56c5742b9e2b 160 int i;
RyoheiHagimoto 0:56c5742b9e2b 161 /*Print a list of the valid (uncorrupt) codewords.*/
RyoheiHagimoto 0:56c5742b9e2b 162 for(i=0;i<32;i++)codes[i]=bch15_5_encode(i);
RyoheiHagimoto 0:56c5742b9e2b 163 for(i=0;i<32;i++)printf("0x%04X%s",codes[i],i+1<32?" ":"\n");
RyoheiHagimoto 0:56c5742b9e2b 164 /*Try to decode all receivable (possibly corrupt) codewords.*/
RyoheiHagimoto 0:56c5742b9e2b 165 for(i=0;i<0x8000;i++){
RyoheiHagimoto 0:56c5742b9e2b 166 unsigned y;
RyoheiHagimoto 0:56c5742b9e2b 167 unsigned z;
RyoheiHagimoto 0:56c5742b9e2b 168 int nerrors;
RyoheiHagimoto 0:56c5742b9e2b 169 int j;
RyoheiHagimoto 0:56c5742b9e2b 170 y=i;
RyoheiHagimoto 0:56c5742b9e2b 171 nerrors=bch15_5_correct(&y);
RyoheiHagimoto 0:56c5742b9e2b 172 z=closest(i);
RyoheiHagimoto 0:56c5742b9e2b 173 if(nerrors<0){
RyoheiHagimoto 0:56c5742b9e2b 174 printf("0x%04X->Failed\n",i);
RyoheiHagimoto 0:56c5742b9e2b 175 if(hamming(i,z)<=3)printf("Error: 0x%04X should map to 0x%04X\n",i,z);
RyoheiHagimoto 0:56c5742b9e2b 176 }
RyoheiHagimoto 0:56c5742b9e2b 177 else{
RyoheiHagimoto 0:56c5742b9e2b 178 printf("0x%04X->0x%04X\n",i,y);
RyoheiHagimoto 0:56c5742b9e2b 179 if(z!=y)printf("Error: 0x%04X should map to 0x%04X\n",i,z);
RyoheiHagimoto 0:56c5742b9e2b 180 }
RyoheiHagimoto 0:56c5742b9e2b 181 }
RyoheiHagimoto 0:56c5742b9e2b 182 return 0;
RyoheiHagimoto 0:56c5742b9e2b 183 }
RyoheiHagimoto 0:56c5742b9e2b 184 #endif
RyoheiHagimoto 0:56c5742b9e2b 185