sys/src/cmd/qr.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <ctype.h>
   4
   5 enum {
   6         NUM = 1,
   7         ANUM = 2,
   8         BYTE = 4,
   9 };
  10
  11 static uchar gpexp[255] =
  12 {1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76,
  13 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157,
  14 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35,
  15 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222,
  16 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60,
  17 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163,
  18 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52,
  19 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59,
  20 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218,
  21 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85,
  22 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198,
  23 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171,
  24 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25,
  25 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81,
  26 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9,
  27 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11,
  28 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71,
  29 142};
  30
  31 static uchar gplog[256] =
  32 {0, 0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4, 100,
  33 224, 14, 52, 141, 239, 129, 28, 193, 105, 248, 200, 8, 76, 113, 5,
  34 138, 101, 47, 225, 36, 15, 33, 53, 147, 142, 218, 240, 18, 130, 69,
  35 29, 181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228, 114,
  36 166, 6, 191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16, 145,
  37 34, 136, 54, 208, 148, 206, 143, 150, 219, 189, 241, 210, 19, 92,
  38 131, 56, 70, 64, 30, 66, 182, 163, 195, 72, 126, 110, 107, 58, 40,
  39 84, 250, 133, 186, 61, 202, 94, 155, 159, 10, 21, 121, 43, 78, 212,
  40 229, 172, 115, 243, 167, 87, 7, 112, 192, 247, 140, 128, 99, 13, 103,
  41 74, 222, 237, 49, 197, 254, 24, 227, 165, 153, 119, 38, 184, 180,
  42 124, 17, 68, 146, 217, 35, 32, 137, 46, 55, 63, 209, 91, 149, 188,
  43 207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242, 86, 211, 171,
  44 20, 42, 93, 158, 132, 60, 57, 83, 71, 109, 65, 162, 31, 45, 67, 216,
  45 183, 123, 164, 118, 196, 23, 73, 236, 127, 12, 111, 246, 108, 161,
  46 59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 203,
  47 89, 95, 176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 215,
  48 79, 174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168, 80,
  49 88, 175};
  50
  51 static uchar *polys[69];
  52 static int cap[160];
  53 static uchar *blocks[160];
  54
  55 static uchar side[40] = {
  56         21, 25, 29, 33, 37, 41, 45, 49,
  57         53, 57, 61, 65, 69, 73, 77, 81,
  58         85, 89, 93, 97, 101, 105, 109, 113,
  59         117, 121, 125, 129, 133, 137, 141, 145,
  60         149, 153, 157, 161, 165, 169, 173, 177
  61 };
  62
  63 static uchar align[40][8] = {
  64         {0},
  65         {6, 18, 0},
  66         {6, 22, 0},
  67         {6, 26, 0},
  68         {6, 30, 0},
  69         {6, 34, 0},
  70         {6, 22, 38, 0},
  71         {6, 24, 42, 0},
  72         {6, 26, 46, 0},
  73         {6, 28, 50, 0},
  74         {6, 30, 54, 0},
  75         {6, 32, 58, 0},
  76         {6, 34, 62, 0},
  77         {6, 26, 46, 66, 0},
  78         {6, 26, 48, 70, 0},
  79         {6, 26, 50, 74, 0},
  80         {6, 30, 54, 78, 0},
  81         {6, 30, 56, 82, 0},
  82         {6, 30, 58, 86, 0},
  83         {6, 34, 62, 90, 0},
  84         {6, 28, 50, 72, 94, 0},
  85         {6, 26, 50, 74, 98, 0},
  86         {6, 30, 54, 78, 102, 0},
  87         {6, 28, 54, 80, 106, 0},
  88         {6, 32, 58, 84, 110, 0},
  89         {6, 30, 58, 86, 114, 0},
  90         {6, 34, 62, 90, 118, 0},
  91         {6, 26, 50, 74, 98, 122, 0},
  92         {6, 30, 54, 78, 102, 126, 0},
  93         {6, 26, 52, 78, 104, 130, 0},
  94         {6, 30, 56, 82, 108, 134, 0},
  95         {6, 34, 60, 86, 112, 138, 0},
  96         {6, 30, 58, 86, 114, 142, 0},
  97         {6, 34, 62, 90, 118, 146, 0},
  98         {6, 30, 54, 78, 102, 126, 150, 0},
  99         {6, 24, 50, 76, 102, 128, 154, 0},
 100         {6, 28, 54, 80, 106, 132, 158, 0},
 101         {6, 32, 58, 84, 110, 136, 162, 0},
 102         {6, 26, 54, 82, 110, 138, 166, 0},
 103         {6, 30, 58, 86, 114, 142, 170, 0},
 104 };
 105
 106 static void
 107 qrinit(void)
 108 {
 109         uchar *p;
 110         int in;
 111         extern uchar qrrawpolys[];
 112         extern uchar qrsizes[];
 113
 114         in = 0;
 115         for(p = qrrawpolys; in || *p != 0; p++){
 116                 if(!in)
 117                         polys[*p] = p + 1;
 118                 in = *p;
 119         }
 120         memset(cap, 0, sizeof(cap));
 121         for(p = qrsizes; p[0] != 0 || p[1] != 0; p += 4){
 122                 cap[p[0]] += p[1] * p[3];
 123                 if(blocks[p[0]] == nil)
 124                         blocks[p[0]] = p;
 125         }
 126 }
 127
 128 static void
 129 bits(uchar *b, int *elen, int *bctr, ulong data, int n)
 130 {
 131         int l, bc, s;
 132
 133         l = *elen;
 134         bc = *bctr;
 135
 136         s = b[l] << n | data;
 137         bc += n;
 138         while(bc > 8)
 139                 b[l++] = s >> (bc -= 8);
 140         b[l] = s;
 141         if(bc == 8){
 142                 l++;
 143                 bc = 0;
 144         }
 145
 146         *elen = l;
 147         *bctr = bc;
 148 }
 149
 150 static int
 151 getlbits(int version, int mode)
 152 {
 153         if(version <= 9)
 154                 switch(mode){
 155                 case NUM: return 10;
 156                 case ANUM: return 9;
 157                 case BYTE: return 8;
 158                 }
 159         else if(version <= 26)
 160                 switch(mode){
 161                 case NUM: return 12;
 162                 case ANUM: return 11;
 163                 case BYTE: return 16;
 164                 }
 165         else
 166                 switch(mode){
 167                 case NUM: return 14;
 168                 case ANUM: return 13;
 169                 case BYTE: return 16;
 170                 }
 171         werrstr("unknown mode %#x", mode);
 172         return -1;
 173 }
 174
 175 static char
 176 atab[] = {
 177         ['0'] 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
 178         ['A'] 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
 179         26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36,
 180         ['a'] 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
 181         26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36,
 182         [' '] 37, ['$'] 38, ['%'] 39, ['*'] 40, ['+'] 41, ['-'] 42,
 183         ['.'] 43, ['/'] 44, [':'] 45
 184 };
 185
 186 static uchar
 187 formsel(int version, int level, int mode, uchar *data, int dlen, int *nchar)
 188 {
 189         int bits, lbits, i, n;
 190
 191         bits = 8;
 192         switch(mode){
 193         case NUM:
 194                 n = 0;
 195                 for(i = 0; i < dlen; i++)
 196                         if(isdigit(data[i]))
 197                                 n++;
 198                 *nchar = n;
 199                 bits += 10 * (n / 3);
 200                 switch(n%3){
 201                 case 1: bits += 4; break;
 202                 case 2: bits += 7; break;
 203                 }
 204                 break;
 205         case ANUM:
 206                 n = 0;
 207                 for(i = 0; i < dlen; i++)
 208                         if(atab[data[i]] != 0)
 209                                 n++;
 210                 *nchar = n;
 211                 bits += 11 * (n >> 1) + 6 * (n & 1);
 212                 break;
 213         case BYTE:
 214                 bits += 8 * dlen;
 215                 *nchar = dlen;
 216                 break;
 217         }
 218         if(version == 0){
 219                 SET(lbits);
 220                 for(i = 0; i < 40; i++){
 221                         if(i == 0 || i == 10 || i == 27){
 222                                 lbits = getlbits(i + 1, mode);
 223                                 if(lbits < 0)
 224                                         return -1;
 225                         }
 226                         if(cap[i << 2 | level] >= (bits + lbits + 7 >> 3))
 227                                 return i << 2 | level;
 228                 }
 229         }else{
 230                 lbits = getlbits(version, mode);
 231                 if(lbits < 0)
 232                         return -1;
 233                 if(cap[version - 1 << 2 | level] >= (bits + lbits + 7 >> 3))
 234                         return version - 1 << 2 | level;
 235         }
 236         werrstr("too many bits");
 237         return -1;
 238 }
 239
 240 static uchar *
 241 encode(uchar verlev, uchar *data, int dlen, int mode, int nchar)
 242 {
 243         uchar *b;
 244         int bc, n, c, nd;
 245         int acc;
 246
 247         n = 0;
 248         c = cap[verlev];
 249         b = malloc(c);
 250         if(b == nil)
 251                 return nil;
 252         bits(b, &n, &bc, mode, 4);
 253         bits(b, &n, &bc, nchar, getlbits((verlev >> 2) + 1, mode));
 254         switch(mode){
 255         case NUM:
 256                 nd = 0;
 257                 acc = 0;
 258                 for(; dlen-- != 0; data++)
 259                         if(isdigit(*data)){
 260                                 acc = acc * 10 + *data - '0';
 261                                 if(++nd == 3){
 262                                         nd = 0;
 263                                         bits(b, &n, &bc, acc, 10);
 264                                         acc = 0;
 265                                 }
 266                         }
 267                 if(nd == 1)
 268                         bits(b, &n, &bc, acc, 4);
 269                 else if(nd == 2)
 270                         bits(b, &n, &bc, acc, 7);
 271                 break;
 272         case ANUM:
 273                 nd = 0;
 274                 acc = 0;
 275                 for(; dlen-- != 0; data++)
 276                         if(atab[*data] != 0){
 277                                 acc = acc * 45 + atab[*data] - 1;
 278                                 if(++nd == 2){
 279                                         nd = 0;
 280                                         bits(b, &n, &bc, acc, 11);
 281                                         acc = 0;
 282                                 }
 283                         }
 284                 if(nd == 1)
 285                         bits(b, &n, &bc, acc, 6);
 286                 break;
 287         case BYTE:
 288                 while(dlen-- != 0)
 289                         bits(b, &n, &bc, *data++, 8);
 290                 break;
 291         default:
 292                 werrstr("unknown mode %#x", mode);
 293                 return nil;
 294         }
 295         bits(b, &n, &bc, 0, 4);
 296         if(bc != 0)
 297                 b[n++] <<= 8 - bc;
 298         while(n < c){
 299                 b[n++] = 0xec;
 300                 if(n == c)
 301                         break;
 302                 b[n++] = 0x11;
 303         }
 304         return b;
 305 }
 306
 307 /* all stored highest coefficient first
 308    poly stored as log and highest coefficient implicit 1 */
 309 static int
 310 ecc(uchar *data, int dl, uchar *poly, uchar *err, int el, int str)
 311 {
 312         uchar *q;
 313         uchar *dp;
 314         uchar l;
 315         int i, x;
 316
 317         q = malloc(el);
 318         if(q == nil)
 319                 return -1;
 320         for(i = 0; i < el; i++){
 321                 q[i] = gpexp[poly[i]];
 322                 err[i * str] = 0;
 323         }
 324         for(dp = data + dl - 1; dp != data - 1; dp--){
 325                 if(*dp != 0){
 326                         l = gplog[*dp];
 327                         for(i = 0; i < el; i++){
 328                                 if(q[i] != 0){
 329                                         x = gplog[q[i]] + l;
 330                                         if(x >= 255)
 331                                                 x -= 255;
 332                                         err[i * str] ^= gpexp[x];
 333                                 }
 334                         }
 335                 }
 336                 l = q[0];
 337                 if(l != 0){
 338                         l = gplog[l];
 339                         for(i = 0; i < el; i++){
 340                                 x = l + poly[i];
 341                                 if(x >= 255)
 342                                         x -= 255;
 343                                 q[i] = (i == el-1 ? 0 : q[i+1]) ^ gpexp[x];
 344                         }
 345                 }else{
 346                         for(i = 0; i < el - 1; i++)
 347                                 q[i] = q[i+1];
 348                         q[el - 1] = 0;
 349                 }
 350         }
 351         free(q);
 352         return 0;
 353 }
 354
 355 static uchar *
 356 codewords(uchar verlev, uchar *data, int *ncp)
 357 {
 358         uchar *bp, *p, *dp, *r, *rp;
 359         uchar *ep;
 360         int ne, i, j, el, nc, nb, ncol;
 361
 362         bp = blocks[verlev];
 363         el = bp[2] - bp[3]; /* guaranteed constant */
 364         ncol = 0;
 365         for(p = bp, ne = 0, nc = 0, nb = 0; p[0] == verlev; p += 4){
 366                 nb += p[1];
 367                 ne += p[1] * el;
 368                 nc += p[1] * p[2];
 369                 ncol = p[3];
 370         }
 371         r = malloc(nc);
 372         if(r == nil)
 373                 return nil;
 374         for(p = bp, dp = data, ep = r + nc - ne; p[0] == verlev; p += 4)
 375                 for(j = 0; j < p[1]; j++){
 376                         if(ecc(dp, p[3], polys[el], ep, el, nb) < 0){
 377                                 free(r);
 378                                 return nil;
 379                         }
 380                         dp += p[3];
 381                         ep++;
 382                 }
 383         for(i = 0, rp = r; i < ncol; i++){
 384                 dp = data + i;
 385                 for(p = bp; p[0] == verlev; p += 4){
 386                         for(j = 0; j < p[1]; j++){
 387                                 if(p[3] > i)
 388                                         *rp++ = *dp;
 389                                 dp += p[3];
 390                         }
 391                 }
 392         }
 393         *ncp = nc;
 394         return r;
 395 }
 396
 397 #define max(i,j) ((i)>(j)?(i):(j))
 398
 399 uchar *
 400 basepat(int verlev)
 401 {
 402         int s, i, j, d;
 403         uchar *pat, *p, *ap, *aq;
 404
 405         s = side[verlev >> 2];
 406         pat = malloc((s + 8) * (s + 8));
 407         if(pat == nil)
 408                 return nil;
 409         p = pat;
 410         for(j = -4; j < s + 4; j++)
 411                 for(i = -4; i < s + 4; i++){
 412                         if(i < 0 || j < 0 || i >= s || j >= s)
 413                                 *p++ = 0xff;
 414                         else if(i < 8 && j < 8 || i >= s - 8 && j < 8 || i < 8 && j >= s - 8){
 415                                 d = max(abs(i >= 8 ? i - s + 4 : i-3), abs(j >= 8 ? j - s + 4 : j-3));
 416                                 *p++ = d == 2 || d == 4 ? 0xff : 0;
 417                         }else if(i == 6 || j == 6)
 418                                 *p++ = (i + j & 1) != 0 ? 0xff : 0;
 419                         else if(i <= 8 && j <= 8 || i <= 8 && j >= s - 8 || i >= s - 8 && j <= 8)
 420                                 *p++ = 0xd0;
 421                         else if(verlev >= 24 && (j >= s - 11 && i < 6 || i >= s - 11 && j < 6))
 422                                 *p++ = 0xc0;
 423                         else
 424                                 *p++ = 0x80;
 425                 }
 426         for(ap = align[verlev >> 2]; *ap != 0; ap++)
 427                 for(aq = align[verlev >> 2]; *aq != 0; aq++){
 428                         if(*ap == 6 && *aq == 6 || *ap >= s - 7 && *aq == 6 || *ap == 6 && *aq >= s - 7)
 429                                 continue;
 430                         for(i = *ap - 2; i <= *ap + 2; i++)
 431                                 for(j = *aq - 2; j <= *aq + 2; j++)
 432                                         pat[i * (s + 8) + j + 4 + (s + 8) * 4] = max(abs(i - *ap), abs(j - *aq)) == 1 ? 0xff : 0;
 433                 }
 434         return pat;
 435 }
 436
 437 static void
 438 fill(uchar verlev, uchar *p, uchar *d, int nc)
 439 {
 440         int s, x, y, i, up;
 441         uchar *dp, db;
 442
 443         s = side[verlev >> 2] + 8;
 444         x = s - 5;
 445         y = s - 5;
 446         up = 1;
 447         SET(db);
 448         for(dp = d, i = 0;;){
 449                 if(i == 0){
 450                         if(dp - d == nc)
 451                                 db = 0;
 452                         else
 453                                 db = *dp++;
 454                 }
 455                 i = i + 1 & 7;
 456                 while(p[y * s + x] != 0x80){
 457                         if(up){
 458                                 if((x & 1 ^ (x < 10)) == 0)
 459                                         x--;
 460                                 else if(y >= 4){
 461                                         x++;
 462                                         y--;
 463                                 }else{
 464                                         x--;
 465                                         up = 0;
 466                                         if(x == 10)
 467                                                 x--;
 468                                 }
 469                         }else{
 470                                 if((x & 1 ^ (x < 10)) == 0)
 471                                         x--;
 472                                 else if(y < s - 4){
 473                                         x++;
 474                                         y++;
 475                                 }else{
 476                                         x--;
 477                                         up = 1;
 478                                         if(x == 10)
 479                                                 x--;
 480                                 }
 481                         }
 482                         if(x < 0)
 483                                 return;
 484                 }
 485                 p[y * s + x] = ~((char)db >> 7) ^ 0x0f;
 486                 db <<= 1;
 487         }
 488 }
 489
 490 static void
 491 mask(uchar verlev, uchar *p, int m)
 492 {
 493         uchar *q;
 494         int s, i, j;
 495
 496         s = side[verlev >> 2];
 497         for(i = -4, q = p; i < s + 4; i++)
 498                 for(j = -4; j < s + 4; j++, q++)
 499                         if(((*q ^ *q >> 4) & 15) == 15)
 500                                 switch(m){
 501                                 case 0: *q ^= (char)((i+j+1) << 7) >> 7; break;
 502                                 case 1: *q ^= (char)((i+1) << 7) >> 7; break;
 503                                 case 2: *q ^= (char)(j % 3 - 1) >> 7; break;
 504                                 case 3: *q ^= (char)((i+j) % 3 - 1) >> 7; break;
 505                                 case 4: *q ^= (char)(((i/2)+(j/3)+1) << 7) >> 7; break;
 506                                 case 5: *q ^= (char)((i*j%2)+(i*j%3) - 1) >> 7; break;
 507                                 case 6: *q ^= (char)((i*j+(i*j%3)+1) << 7) >> 7; break;
 508                                 case 7: *q ^= (char)((i+j+(i*j%3)+1) << 7) >> 7; break;
 509                                 }
 510 }
 511
 512 static int
 513 evaluate(uchar verlev, uchar *p)
 514 {
 515         int r, i, j, l, s, sc, cnt;
 516         uchar q, sh;
 517         uchar *pp;
 518         enum {
 519                 N1 = 3,
 520                 N2 = 3,
 521                 N3 = 40,
 522                 N4 = 10,
 523         };
 524
 525         s = side[verlev >> 2];
 526         sc = 0;
 527         cnt = 0;
 528
 529         for(i = 0; i < s; i++){
 530                 r = 0;
 531                 l = -1;
 532                 sh = 0;
 533                 for(j = 0; j < s; j++){
 534                         q = p[i * (s + 8) + j + 4 + (s + 8) * 4] >= 0x80;
 535                         cnt += q;
 536                         sh = sh << 1 | l;
 537                         if(q != l){
 538                                 if(r >= 5)
 539                                         sc += N1 + r;
 540                                 l = q;
 541                                 r = 0;
 542                         }
 543                         if((sh & 0x7f) == 0x5d)
 544                                 sc += N3;
 545                 }
 546                 if(r >= 5)
 547                         sc += N1 * r;
 548         }
 549         sc = abs(cnt - s * s / 2) / (s * s / 20) * N4;
 550
 551         for(j = 0; j < s; j++){
 552                 r = 0;
 553                 l = -1;
 554                 sh = 0;
 555                 for(i = 0; i < s; i++){
 556                         q = p[i * (s + 8) + j + 4 + (s + 8) * 4];
 557                         sh = sh << 1 | l;
 558                         if(q != l){
 559                                 if(r >= 5)
 560                                         sc += N1 + r;
 561                                 l = q;
 562                                 r = 0;
 563                         }
 564                         if((sh & 0x7f) == 0x5d)
 565                                 sc += N3;
 566                 }
 567                 if(r >= 5)
 568                         sc += N1 * r;
 569         }
 570
 571         /* approximation */
 572         for(j = 1; j < s; j++)
 573                 for(i = 1; i < s; i++){
 574                         pp = p + i * (s + 8) + j + 4 + (s + 8) * 4;
 575                         if(pp[0] == pp[-1] && pp[0] == pp[-(s+8)] && pp[0] == pp[-1-(s+8)])
 576                                 sc += N2;
 577                 }
 578         return sc;
 579 }
 580
 581 static void
 582 format(uchar verlev, uchar *p, int m)
 583 {
 584         static ushort format[] =
 585                 {21522, 20773, 24188, 23371, 17913, 16590, 20375, 19104, 30660,
 586                 29427, 32170, 30877, 26159, 25368, 27713, 26998, 5769, 5054, 7399,
 587                 6608, 1890, 597, 3340, 2107, 13663, 12392, 16177, 14854, 9396, 8579,
 588                 11994, 11245};
 589         int s, i;
 590         ushort f;
 591         uchar c;
 592
 593         s = side[verlev >> 2];
 594         f = ~format[verlev << 3 & 0x18 ^ 8 | m];
 595         for(i = 0; i < 15; i++){
 596                 c = (char)(f << 7) >> 7;
 597                 if(i < 8){
 598                         p[(i + (i >= 6)) * (s + 8) + 8 + 4 + (s + 8) * 4] = c;
 599                         p[12 * (s + 8) + (s + 3 - i)] = c;
 600                 }else{
 601                         p[(s - 15 + i) * (s + 8) + 8 + 4 + (s + 8) * 4] = c;
 602                         p[12 * (s + 8) + (18 - i + (i == 8))] = c;
 603                 }
 604                 f >>= 1;
 605         }
 606         p[(s - 8) * (s + 8) + 8 + 4 + (s + 8) * 4] = 0;
 607 }
 608
 609 static void
 610 version(uchar verlev, uchar *p)
 611 {
 612         int s, i, f, q;
 613         uchar c;
 614         static int version[] = {
 615                 0x07C94, 0x085BC, 0x09A99, 0x0A4D3, 0x0BBF6, 0x0C762, 0x0D847,
 616                 0x0E60D, 0x0F928, 0x10B78, 0x1145D, 0x12A17, 0x13532, 0x149A6,
 617                 0x15683, 0x168C9, 0x177EC, 0x18EC4, 0x191E1, 0x1AFAB, 0x1B08E,
 618                 0x1CC1A, 0x1D33F, 0x1ED75, 0x1F250, 0x209D5, 0x216F0, 0x228BA,
 619                 0x2379F, 0x24B0B, 0x2542E, 0x26A64, 0x27541, 0x28C69
 620         };
 621
 622         if(verlev < 24)
 623                 return;
 624         s = side[verlev >> 2] + 8;
 625         f = ~version[(verlev >> 2) - 6];
 626         for(i = 0; i < 18; i++){
 627                 c = (char)(f << 7) >> 7;
 628                 f >>= 1;
 629                 q = (s - 15 + i % 3) * s + (4 + i / 3);
 630                 p[q] = c;
 631                 p[(q * s) % (s * s - 1)] = c;
 632         }
 633 }
 634
 635 static void
 636 finalize(uchar verlev, uchar *p)
 637 {
 638         int s;
 639
 640         s = side[verlev >> 2] + 8;
 641         s *= s;
 642         while(s--)
 643                 *((char *)p++) >>= 4;
 644 }
 645
 646 uchar *
 647 qrcode(int ver, int level, int mode, uchar *data, int dlen, int *sidep)
 648 {
 649         int s, nc, m, mv, mbest, mval, nchar;
 650         uchar *d, *w, *b;
 651         uchar verlev;
 652
 653         qrinit();
 654         verlev = formsel(ver, level, mode, data, dlen, &nchar);
 655         if(verlev == 0xff)
 656                 return nil;
 657         s = side[verlev >> 2];
 658         d = encode(verlev, data, dlen, mode, nchar);
 659         if(d == nil)
 660                 return nil;
 661         w = codewords(verlev, d, &nc);
 662         free(d);
 663         if(w == nil)
 664                 return nil;
 665         b = basepat(verlev);
 666         if(b == nil){
 667                 free(w);
 668                 return nil;
 669         }
 670         fill(verlev, b, w, nc);
 671         free(w);
 672         SET(mbest); SET(mval);
 673         for(m = 0; m < 8; m++){
 674                 mask(verlev, b, m);
 675                 mv = evaluate(verlev, b);
 676                 if(m == 0 || mv < mval){
 677                         mbest = m;
 678                         mval = mv;
 679                 }
 680                 if(m != 7 || mbest != m)
 681                         mask(verlev, b, m);
 682         }
 683         if(mbest != 7)
 684                 mask(verlev, b, mbest);
 685         format(verlev, b, mbest);
 686         version(verlev, b);
 687         finalize(verlev, b);
 688         *sidep = s + 8;
 689         return b;
 690 }
 691
 692 void
 693 usage(void)
 694 {
 695         fprint(2, "usage: %s [-LMQHn] [-v ver]\n", argv0);
 696         exits("usage");
 697 }
 698
 699 void
 700 main(int argc, char **argv)
 701 {
 702         uchar buf[8192];
 703         int rc;
 704         int ver, lev, mode, s;
 705         char *c;
 706         uchar *b;
 707
 708         ver = 0;
 709         lev = 1;
 710         mode = BYTE;
 711         ARGBEGIN {
 712         case 'L': lev = 0; break;
 713         case 'M': lev = 1; break;
 714         case 'Q': lev = 2; break;
 715         case 'H': lev = 3; break;
 716         case 'v':
 717                 ver = strtol(EARGF(usage()), &c, 0);
 718                 if(*c != 0 || ver < 0 || ver > 40)
 719                         usage();
 720                 break;
 721         case 'n': mode = NUM; break;
 722         case 'a': mode = ANUM; break;
 723         default: usage();
 724         } ARGEND;
 725
 726         if(argc != 0)
 727                 usage();
 728
 729         rc = readn(0, buf, sizeof(buf));
 730         if(rc < 0)
 731                 sysfatal("read: %r");
 732         b = qrcode(ver, lev, mode, buf, rc, &s);
 733         if(b == nil)
 734                 sysfatal("%r");
 735         if(print("%11s %11d %11d %11d %11d ", "k8", 0, 0, s, s) != 5*12)
 736                 sysfatal("print: %r");
 737         if(write(1, b, s*s) != s*s)
 738                 sysfatal("write: %r");
 739         exits(0);
 740 }
 741
 742 uchar qrrawpolys[] = {
 743         7, 87, 229, 146, 149, 238, 102, 21,
 744         0, 10, 251, 67, 46, 61, 118, 70,
 745         64, 94, 32, 45, 0, 13, 74, 152,
 746         176, 100, 86, 100, 106, 104, 130, 218,
 747         206, 140, 78, 0, 15, 8, 183, 61,
 748         91, 202, 37, 51, 58, 58, 237, 140,
 749         124, 5, 99, 105, 0, 16, 120, 104,
 750         107, 109, 102, 161, 76, 3, 91, 191,
 751         147, 169, 182, 194, 225, 120, 0, 17,
 752         43, 139, 206, 78, 43, 239, 123, 206,
 753         214, 147, 24, 99, 150, 39, 243, 163,
 754         136, 0, 18, 215, 234, 158, 94, 184,
 755         97, 118, 170, 79, 187, 152, 148, 252,
 756         179, 5, 98, 96, 153, 0, 20, 17,
 757         60, 79, 50, 61, 163, 26, 187, 202,
 758         180, 221, 225, 83, 239, 156, 164, 212,
 759         212, 188, 190, 0, 22, 210, 171, 247,
 760         242, 93, 230, 14, 109, 221, 53, 200,
 761         74, 8, 172, 98, 80, 219, 134, 160,
 762         105, 165, 231, 0, 24, 229, 121, 135,
 763         48, 211, 117, 251, 126, 159, 180, 169,
 764         152, 192, 226, 228, 218, 111, 117, 232,
 765         87, 96, 227, 21, 0, 26, 173, 125,
 766         158, 2, 103, 182, 118, 17, 145, 201,
 767         111, 28, 165, 53, 161, 21, 245, 142,
 768         13, 102, 48, 227, 153, 145, 218, 70,
 769         0, 28, 168, 223, 200, 104, 224, 234,
 770         108, 180, 110, 190, 195, 147, 205, 27,
 771         232, 201, 21, 43, 245, 87, 42, 195,
 772         212, 119, 242, 37, 9, 123, 0, 30,
 773         41, 173, 145, 152, 216, 31, 179, 182,
 774         50, 48, 110, 86, 239, 96, 222, 125,
 775         42, 173, 226, 193, 224, 130, 156, 37,
 776         251, 216, 238, 40, 192, 180, 0, 32,
 777         10, 6, 106, 190, 249, 167, 4, 67,
 778         209, 138, 138, 32, 242, 123, 89, 27,
 779         120, 185, 80, 156, 38, 69, 171, 60,
 780         28, 222, 80, 52, 254, 185, 220, 241,
 781         0, 34, 111, 77, 146, 94, 26, 21,
 782         108, 19, 105, 94, 113, 193, 86, 140,
 783         163, 125, 58, 158, 229, 239, 218, 103,
 784         56, 70, 114, 61, 183, 129, 167, 13,
 785         98, 62, 129, 51, 0, 36, 200, 183,
 786         98, 16, 172, 31, 246, 234, 60, 152,
 787         115, 167, 152, 113, 248, 238, 107, 18,
 788         63, 218, 37, 87, 210, 105, 177, 120,
 789         74, 121, 196, 117, 251, 113, 233, 30,
 790         120, 0, 40, 59, 116, 79, 161, 252,
 791         98, 128, 205, 128, 161, 247, 57, 163,
 792         56, 235, 106, 53, 26, 187, 174, 226,
 793         104, 170, 7, 175, 35, 181, 114, 88,
 794         41, 47, 163, 125, 134, 72, 20, 232,
 795         53, 35, 15, 0, 42, 250, 103, 221,
 796         230, 25, 18, 137, 231, 3, 58, 242,
 797         221, 191, 110, 84, 230, 8, 188, 106,
 798         96, 147, 15, 131, 139, 34, 101, 223,
 799         39, 101, 213, 199, 237, 254, 201, 123,
 800         171, 162, 194, 117, 50, 96, 0, 44,
 801         190, 7, 61, 121, 71, 246, 69, 55,
 802         168, 188, 89, 243, 191, 25, 72, 123,
 803         9, 145, 14, 247, 238, 44, 78, 143,
 804         62, 224, 126, 118, 114, 68, 163, 52,
 805         194, 217, 147, 204, 169, 37, 130, 113,
 806         102, 73, 181, 0, 46, 112, 94, 88,
 807         112, 253, 224, 202, 115, 187, 99, 89,
 808         5, 54, 113, 129, 44, 58, 16, 135,
 809         216, 169, 211, 36, 4, 96, 60, 241,
 810         73, 104, 234, 8, 249, 245, 119, 174,
 811         52, 25, 157, 224, 43, 202, 223, 19,
 812         82, 15, 0, 48, 228, 25, 196, 130,
 813         211, 146, 60, 24, 251, 90, 39, 102,
 814         240, 61, 178, 63, 46, 123, 115, 18,
 815         221, 111, 135, 160, 182, 205, 107, 206,
 816         95, 150, 120, 184, 91, 21, 247, 156,
 817         140, 238, 191, 11, 94, 227, 84, 50,
 818         163, 39, 34, 108, 0, 50, 232, 125,
 819         157, 161, 164, 9, 118, 46, 209, 99,
 820         203, 193, 35, 3, 209, 111, 195, 242,
 821         203, 225, 46, 13, 32, 160, 126, 209,
 822         130, 160, 242, 215, 242, 75, 77, 42,
 823         189, 32, 113, 65, 124, 69, 228, 114,
 824         235, 175, 124, 170, 215, 232, 133, 205,
 825         0, 52, 116, 50, 86, 186, 50, 220,
 826         251, 89, 192, 46, 86, 127, 124, 19,
 827         184, 233, 151, 215, 22, 14, 59, 145,
 828         37, 242, 203, 134, 254, 89, 190, 94,
 829         59, 65, 124, 113, 100, 233, 235, 121,
 830         22, 76, 86, 97, 39, 242, 200, 220,
 831         101, 33, 239, 254, 116, 51, 0, 54,
 832         183, 26, 201, 87, 210, 221, 113, 21,
 833         46, 65, 45, 50, 238, 184, 249, 225,
 834         102, 58, 209, 218, 109, 165, 26, 95,
 835         184, 192, 52, 245, 35, 254, 238, 175,
 836         172, 79, 123, 25, 122, 43, 120, 108,
 837         215, 80, 128, 201, 235, 8, 153, 59,
 838         101, 31, 198, 76, 31, 156, 0, 56,
 839         106, 120, 107, 157, 164, 216, 112, 116,
 840         2, 91, 248, 163, 36, 201, 202, 229,
 841         6, 144, 254, 155, 135, 208, 170, 209,
 842         12, 139, 127, 142, 182, 249, 177, 174,
 843         190, 28, 10, 85, 239, 184, 101, 124,
 844         152, 206, 96, 23, 163, 61, 27, 196,
 845         247, 151, 154, 202, 207, 20, 61, 10,
 846         0, 58, 82, 116, 26, 247, 66, 27,
 847         62, 107, 252, 182, 200, 185, 235, 55,
 848         251, 242, 210, 144, 154, 237, 176, 141,
 849         192, 248, 152, 249, 206, 85, 253, 142,
 850         65, 165, 125, 23, 24, 30, 122, 240,
 851         214, 6, 129, 218, 29, 145, 127, 134,
 852         206, 245, 117, 29, 41, 63, 159, 142,
 853         233, 125, 148, 123, 0, 60, 107, 140,
 854         26, 12, 9, 141, 243, 197, 226, 197,
 855         219, 45, 211, 101, 219, 120, 28, 181,
 856         127, 6, 100, 247, 2, 205, 198, 57,
 857         115, 219, 101, 109, 160, 82, 37, 38,
 858         238, 49, 160, 209, 121, 86, 11, 124,
 859         30, 181, 84, 25, 194, 87, 65, 102,
 860         190, 220, 70, 27, 209, 16, 89, 7,
 861         33, 240, 0, 62, 65, 202, 113, 98,
 862         71, 223, 248, 118, 214, 94, 122, 37,
 863         23, 2, 228, 58, 121, 7, 105, 135,
 864         78, 243, 118, 70, 76, 223, 89, 72,
 865         50, 70, 111, 194, 17, 212, 126, 181,
 866         35, 221, 117, 235, 11, 229, 149, 147,
 867         123, 213, 40, 115, 6, 200, 100, 26,
 868         246, 182, 218, 127, 215, 36, 186, 110,
 869         106, 0, 64, 45, 51, 175, 9, 7,
 870         158, 159, 49, 68, 119, 92, 123, 177,
 871         204, 187, 254, 200, 78, 141, 149, 119,
 872         26, 127, 53, 160, 93, 199, 212, 29,
 873         24, 145, 156, 208, 150, 218, 209, 4,
 874         216, 91, 47, 184, 146, 47, 140, 195,
 875         195, 125, 242, 238, 63, 99, 108, 140,
 876         230, 242, 31, 204, 11, 178, 243, 217,
 877         156, 213, 231, 0, 66, 5, 118, 222,
 878         180, 136, 136, 162, 51, 46, 117, 13,
 879         215, 81, 17, 139, 247, 197, 171, 95,
 880         173, 65, 137, 178, 68, 111, 95, 101,
 881         41, 72, 214, 169, 197, 95, 7, 44,
 882         154, 77, 111, 236, 40, 121, 143, 63,
 883         87, 80, 253, 240, 126, 217, 77, 34,
 884         232, 106, 50, 168, 82, 76, 146, 67,
 885         106, 171, 25, 132, 93, 45, 105, 0,
 886         68, 247, 159, 223, 33, 224, 93, 77,
 887         70, 90, 160, 32, 254, 43, 150, 84,
 888         101, 190, 205, 133, 52, 60, 202, 165,
 889         220, 203, 151, 93, 84, 15, 84, 253,
 890         173, 160, 89, 227, 52, 199, 97, 95,
 891         231, 52, 177, 41, 125, 137, 241, 166,
 892         225, 118, 2, 54, 32, 82, 215, 175,
 893         198, 43, 238, 235, 27, 101, 184, 127,
 894         3, 5, 8, 163, 238, 0, 0
 895 };
 896
 897 /* (version - 1) * 4 + level, number of blocks, number of bytes in block, number of data bytes */
 898 uchar qrsizes[] = {
 899         0, 1, 26, 19,
 900         1, 1, 26, 16,
 901         2, 1, 26, 13,
 902         3, 1, 26, 9,
 903         4, 1, 44, 34,
 904         5, 1, 44, 28,
 905         6, 1, 44, 22,
 906         7, 1, 44, 16,
 907         8, 1, 70, 55,
 908         9, 1, 70, 44,
 909         10, 2, 35, 17,
 910         11, 2, 35, 13,
 911         12, 1, 100, 80,
 912         13, 2, 50, 32,
 913         14, 2, 50, 24,
 914         15, 4, 25, 9,
 915         16, 1, 134, 108,
 916         17, 2, 67, 43,
 917         18, 2, 33, 15,
 918         18, 2, 34, 16,
 919         19, 2, 33, 11,
 920         19, 2, 34, 12,
 921         20, 2, 86, 68,
 922         21, 4, 43, 27,
 923         22, 4, 43, 19,
 924         23, 4, 43, 15,
 925         24, 2, 98, 78,
 926         25, 4, 49, 31,
 927         26, 2, 32, 14,
 928         26, 4, 33, 15,
 929         27, 4, 39, 13,
 930         27, 1, 40, 14,
 931         28, 2, 121, 97,
 932         29, 2, 60, 38,
 933         29, 2, 61, 39,
 934         30, 4, 40, 18,
 935         30, 2, 41, 19,
 936         31, 4, 40, 14,
 937         31, 2, 41, 15,
 938         32, 2, 146, 116,
 939         33, 3, 58, 36,
 940         33, 2, 59, 37,
 941         34, 4, 36, 16,
 942         34, 4, 37, 17,
 943         35, 4, 36, 12,
 944         35, 4, 37, 13,
 945         36, 2, 86, 68,
 946         36, 2, 87, 69,
 947         37, 4, 69, 43,
 948         37, 1, 70, 44,
 949         38, 6, 43, 19,
 950         38, 2, 44, 20,
 951         39, 6, 43, 15,
 952         39, 2, 44, 16,
 953         40, 4, 101, 81,
 954         41, 1, 80, 50,
 955         41, 4, 81, 51,
 956         42, 4, 50, 22,
 957         42, 4, 51, 23,
 958         43, 3, 36, 12,
 959         43, 8, 37, 13,
 960         44, 2, 116, 92,
 961         44, 2, 117, 93,
 962         45, 6, 58, 36,
 963         45, 2, 59, 37,
 964         46, 4, 46, 20,
 965         46, 6, 47, 21,
 966         47, 7, 42, 14,
 967         47, 4, 43, 15,
 968         48, 4, 133, 107,
 969         49, 8, 59, 37,
 970         49, 1, 60, 38,
 971         50, 8, 44, 20,
 972         50, 4, 45, 21,
 973         51, 12, 33, 11,
 974         51, 4, 34, 12,
 975         52, 3, 145, 115,
 976         52, 1, 146, 116,
 977         53, 4, 64, 40,
 978         53, 5, 65, 41,
 979         54, 11, 36, 16,
 980         54, 5, 37, 17,
 981         55, 11, 36, 12,
 982         55, 5, 37, 13,
 983         56, 5, 109, 87,
 984         56, 1, 110, 88,
 985         57, 5, 65, 41,
 986         57, 5, 66, 42,
 987         58, 5, 54, 24,
 988         58, 7, 55, 25,
 989         59, 11, 36, 12,
 990         59, 7, 37, 13,
 991         60, 5, 122, 98,
 992         60, 1, 123, 99,
 993         61, 7, 73, 45,
 994         61, 3, 74, 46,
 995         62, 15, 43, 19,
 996         62, 2, 44, 20,
 997         63, 3, 45, 15,
 998         63, 13, 46, 16,
 999         64, 1, 135, 107,
1000         64, 5, 136, 108,
1001         65, 10, 74, 46,
1002         65, 1, 75, 47,
1003         66, 1, 50, 22,
1004         66, 15, 51, 23,
1005         67, 2, 42, 14,
1006         67, 17, 43, 15,
1007         68, 5, 150, 120,
1008         68, 1, 151, 121,
1009         69, 9, 69, 43,
1010         69, 4, 70, 44,
1011         70, 17, 50, 22,
1012         70, 1, 51, 23,
1013         71, 2, 42, 14,
1014         71, 19, 43, 15,
1015         72, 3, 141, 113,
1016         72, 4, 142, 114,
1017         73, 3, 70, 44,
1018         73, 11, 71, 45,
1019         74, 17, 47, 21,
1020         74, 4, 48, 22,
1021         75, 9, 39, 13,
1022         75, 16, 40, 14,
1023         76, 3, 135, 107,
1024         76, 5, 136, 108,
1025         77, 3, 67, 41,
1026         77, 13, 68, 42,
1027         78, 15, 54, 24,
1028         78, 5, 55, 25,
1029         79, 15, 43, 15,
1030         79, 10, 44, 16,
1031         80, 4, 144, 116,
1032         80, 4, 145, 117,
1033         81, 17, 68, 42,
1034         82, 17, 50, 22,
1035         82, 6, 51, 23,
1036         83, 19, 46, 16,
1037         83, 6, 47, 17,
1038         84, 2, 139, 111,
1039         84, 7, 140, 112,
1040         85, 17, 74, 46,
1041         86, 7, 54, 24,
1042         86, 16, 55, 25,
1043         87, 34, 37, 13,
1044         88, 4, 151, 121,
1045         88, 5, 152, 122,
1046         89, 4, 75, 47,
1047         89, 14, 76, 48,
1048         90, 11, 54, 24,
1049         90, 14, 55, 25,
1050         91, 16, 45, 15,
1051         91, 14, 46, 16,
1052         92, 6, 147, 117,
1053         92, 4, 148, 118,
1054         93, 6, 73, 45,
1055         93, 14, 74, 46,
1056         94, 11, 54, 24,
1057         94, 16, 55, 25,
1058         95, 30, 46, 16,
1059         95, 2, 47, 17,
1060         96, 8, 132, 106,
1061         96, 4, 133, 107,
1062         97, 8, 75, 47,
1063         97, 13, 76, 48,
1064         98, 7, 54, 24,
1065         98, 22, 55, 25,
1066         99, 22, 45, 15,
1067         99, 13, 46, 16,
1068         100, 10, 142, 114,
1069         100, 2, 143, 115,
1070         101, 19, 74, 46,
1071         101, 4, 75, 47,
1072         102, 28, 50, 22,
1073         102, 6, 51, 23,
1074         103, 33, 46, 16,
1075         103, 4, 47, 17,
1076         104, 8, 152, 122,
1077         104, 4, 153, 123,
1078         105, 22, 73, 45,
1079         105, 3, 74, 46,
1080         106, 8, 53, 23,
1081         106, 26, 54, 24,
1082         107, 12, 45, 15,
1083         107, 28, 46, 16,
1084         108, 3, 147, 117,
1085         108, 10, 148, 118,
1086         109, 3, 73, 45,
1087         109, 23, 74, 46,
1088         110, 4, 54, 24,
1089         110, 31, 55, 25,
1090         111, 11, 45, 15,
1091         111, 31, 46, 16,
1092         112, 7, 146, 116,
1093         112, 7, 147, 117,
1094         113, 21, 73, 45,
1095         113, 7, 74, 46,
1096         114, 1, 53, 23,
1097         114, 37, 54, 24,
1098         115, 19, 45, 15,
1099         115, 26, 46, 16,
1100         116, 5, 145, 115,
1101         116, 10, 146, 116,
1102         117, 19, 75, 47,
1103         117, 10, 76, 48,
1104         118, 15, 54, 24,
1105         118, 25, 55, 25,
1106         119, 23, 45, 15,
1107         119, 25, 46, 16,
1108         120, 13, 145, 115,
1109         120, 3, 146, 116,
1110         121, 2, 74, 46,
1111         121, 29, 75, 47,
1112         122, 42, 54, 24,
1113         122, 1, 55, 25,
1114         123, 23, 45, 15,
1115         123, 28, 46, 16,
1116         124, 17, 145, 115,
1117         125, 10, 74, 46,
1118         125, 23, 75, 47,
1119         126, 10, 54, 24,
1120         126, 35, 55, 25,
1121         127, 19, 45, 15,
1122         127, 35, 46, 16,
1123         128, 17, 145, 115,
1124         128, 1, 146, 116,
1125         129, 14, 74, 46,
1126         129, 21, 75, 47,
1127         130, 29, 54, 24,
1128         130, 19, 55, 25,
1129         131, 11, 45, 15,
1130         131, 46, 46, 16,
1131         132, 13, 145, 115,
1132         132, 6, 146, 116,
1133         133, 14, 74, 46,
1134         133, 23, 75, 47,
1135         134, 44, 54, 24,
1136         134, 7, 55, 25,
1137         135, 59, 46, 16,
1138         135, 1, 47, 17,
1139         136, 12, 151, 121,
1140         136, 7, 152, 122,
1141         137, 12, 75, 47,
1142         137, 26, 76, 48,
1143         138, 39, 54, 24,
1144         138, 14, 55, 25,
1145         139, 22, 45, 15,
1146         139, 41, 46, 16,
1147         140, 6, 151, 121,
1148         140, 14, 152, 122,
1149         141, 6, 75, 47,
1150         141, 34, 76, 48,
1151         142, 46, 54, 24,
1152         142, 10, 55, 25,
1153         143, 2, 45, 15,
1154         143, 64, 46, 16,
1155         144, 17, 152, 122,
1156         144, 4, 153, 123,
1157         145, 29, 74, 46,
1158         145, 14, 75, 47,
1159         146, 49, 54, 24,
1160         146, 10, 55, 25,
1161         147, 24, 45, 15,
1162         147, 46, 46, 16,
1163         148, 4, 152, 122,
1164         148, 18, 153, 123,
1165         149, 13, 74, 46,
1166         149, 32, 75, 47,
1167         150, 48, 54, 24,
1168         150, 14, 55, 25,
1169         151, 42, 45, 15,
1170         151, 32, 46, 16,
1171         152, 20, 147, 117,
1172         152, 4, 148, 118,
1173         153, 40, 75, 47,
1174         153, 7, 76, 48,
1175         154, 43, 54, 24,
1176         154, 22, 55, 25,
1177         155, 10, 45, 15,
1178         155, 67, 46, 16,
1179         156, 19, 148, 118,
1180         156, 6, 149, 119,
1181         157, 18, 75, 47,
1182         157, 31, 76, 48,
1183         158, 34, 54, 24,
1184         158, 34, 55, 25,
1185         159, 20, 45, 15,
1186         159, 61, 46, 16,
1187         0, 0, 0, 0,
1188 };