QRScanner/mobile/jni/thirdparty/jbig2dec/jbig2_mmr.c

   1 /* Copyright (C) 2001-2012 Artifex Software, Inc.
   2    All Rights Reserved.
   3
   4    This software is provided AS-IS with no warranty, either express or
   5    implied.
   6
   7    This software is distributed under license and may not be copied,
   8    modified or distributed except as expressly authorized under the terms
   9    of the license contained in the file LICENSE in this distribution.
  10
  11    Refer to licensing information at http://www.artifex.com or contact
  12    Artifex Software, Inc.,  7 Mt. Lassen Drive - Suite A-134, San Rafael,
  13    CA  94903, U.S.A., +1(415)492-9861, for further information.
  14 */
  15
  16 /*
  17     jbig2dec
  18 */
  19
  20
  21 /* An implementation of MMR decoding. This is based on the
  22    implementation in Fitz, which in turn is based on the one
  23    in Ghostscript.
  24 */
  25
  26 #ifdef HAVE_CONFIG_H
  27 #include "config.h"
  28 #endif
  29 #include "os_types.h"
  30
  31 #include <stddef.h>
  32 #include <stdio.h>
  33 #include <string.h>
  34
  35 #include "jbig2.h"
  36 #include "jbig2_priv.h"
  37 #include "jbig2_arith.h"
  38 #include "jbig2_generic.h"
  39 #include "jbig2_mmr.h"
  40
  41 typedef struct {
  42         int width;
  43         int height;
  44         const byte *data;
  45         size_t size;
  46         int data_index;
  47         int bit_index;
  48         uint32_t word;
  49 } Jbig2MmrCtx;
  50
  51
  52 static void
  53 jbig2_decode_mmr_init(Jbig2MmrCtx *mmr, int width, int height, const byte *data, size_t size)
  54 {
  55         int i;
  56         uint32_t word = 0;
  57
  58         mmr->width = width;
  59         mmr->height = height;
  60         mmr->data = data;
  61         mmr->size = size;
  62         mmr->data_index = 0;
  63         mmr->bit_index = 0;
  64
  65         for (i = 0; i < size && i < 4; i++)
  66                 word |= (data[i] << ((3 - i) << 3));
  67         mmr->word = word;
  68 }
  69
  70 static void
  71 jbig2_decode_mmr_consume(Jbig2MmrCtx *mmr, int n_bits)
  72 {
  73         mmr->word <<= n_bits;
  74         mmr->bit_index += n_bits;
  75         while (mmr->bit_index >= 8) {
  76                 mmr->bit_index -= 8;
  77                 if (mmr->data_index + 4 < mmr->size)
  78                         mmr->word |= (mmr->data[mmr->data_index + 4] << mmr->bit_index);
  79                 mmr->data_index++;
  80         }
  81 }
  82
  83 /*
  84 <raph> the first 2^(initialbits) entries map bit patterns to decodes
  85 <raph> let's say initial_bits is 8 for the sake of example
  86 <raph> and that the code is 1001
  87 <raph> that means that entries 0x90 .. 0x9f have the entry { val, 4 }
  88 <raph> because those are all the bytes that start with the code
  89 <raph> and the 4 is the length of the code
  90 ... if (n_bits > initial_bits) ...
  91 <raph> anyway, in that case, it basically points to a mini table
  92 <raph> the n_bits is the maximum length of all codes beginning with that byte
  93 <raph> so 2^(n_bits - initial_bits) is the size of the mini-table
  94 <raph> peter came up with this, and it makes sense
  95 */
  96
  97 typedef struct {
  98         short val;
  99         short n_bits;
 100 } mmr_table_node;
 101
 102 /* white decode table (runlength huffman codes) */
 103 const mmr_table_node jbig2_mmr_white_decode[] = {
 104 { 256, 12 },
 105 { 272, 12 },
 106 { 29, 8 },
 107 { 30, 8 },
 108 { 45, 8 },
 109 { 46, 8 },
 110 { 22, 7 },
 111 { 22, 7 },
 112 { 23, 7 },
 113 { 23, 7 },
 114 { 47, 8 },
 115 { 48, 8 },
 116 { 13, 6 },
 117 { 13, 6 },
 118 { 13, 6 },
 119 { 13, 6 },
 120 { 20, 7 },
 121 { 20, 7 },
 122 { 33, 8 },
 123 { 34, 8 },
 124 { 35, 8 },
 125 { 36, 8 },
 126 { 37, 8 },
 127 { 38, 8 },
 128 { 19, 7 },
 129 { 19, 7 },
 130 { 31, 8 },
 131 { 32, 8 },
 132 { 1, 6 },
 133 { 1, 6 },
 134 { 1, 6 },
 135 { 1, 6 },
 136 { 12, 6 },
 137 { 12, 6 },
 138 { 12, 6 },
 139 { 12, 6 },
 140 { 53, 8 },
 141 { 54, 8 },
 142 { 26, 7 },
 143 { 26, 7 },
 144 { 39, 8 },
 145 { 40, 8 },
 146 { 41, 8 },
 147 { 42, 8 },
 148 { 43, 8 },
 149 { 44, 8 },
 150 { 21, 7 },
 151 { 21, 7 },
 152 { 28, 7 },
 153 { 28, 7 },
 154 { 61, 8 },
 155 { 62, 8 },
 156 { 63, 8 },
 157 { 0, 8 },
 158 { 320, 8 },
 159 { 384, 8 },
 160 { 10, 5 },
 161 { 10, 5 },
 162 { 10, 5 },
 163 { 10, 5 },
 164 { 10, 5 },
 165 { 10, 5 },
 166 { 10, 5 },
 167 { 10, 5 },
 168 { 11, 5 },
 169 { 11, 5 },
 170 { 11, 5 },
 171 { 11, 5 },
 172 { 11, 5 },
 173 { 11, 5 },
 174 { 11, 5 },
 175 { 11, 5 },
 176 { 27, 7 },
 177 { 27, 7 },
 178 { 59, 8 },
 179 { 60, 8 },
 180 { 288, 9 },
 181 { 290, 9 },
 182 { 18, 7 },
 183 { 18, 7 },
 184 { 24, 7 },
 185 { 24, 7 },
 186 { 49, 8 },
 187 { 50, 8 },
 188 { 51, 8 },
 189 { 52, 8 },
 190 { 25, 7 },
 191 { 25, 7 },
 192 { 55, 8 },
 193 { 56, 8 },
 194 { 57, 8 },
 195 { 58, 8 },
 196 { 192, 6 },
 197 { 192, 6 },
 198 { 192, 6 },
 199 { 192, 6 },
 200 { 1664, 6 },
 201 { 1664, 6 },
 202 { 1664, 6 },
 203 { 1664, 6 },
 204 { 448, 8 },
 205 { 512, 8 },
 206 { 292, 9 },
 207 { 640, 8 },
 208 { 576, 8 },
 209 { 294, 9 },
 210 { 296, 9 },
 211 { 298, 9 },
 212 { 300, 9 },
 213 { 302, 9 },
 214 { 256, 7 },
 215 { 256, 7 },
 216 { 2, 4 },
 217 { 2, 4 },
 218 { 2, 4 },
 219 { 2, 4 },
 220 { 2, 4 },
 221 { 2, 4 },
 222 { 2, 4 },
 223 { 2, 4 },
 224 { 2, 4 },
 225 { 2, 4 },
 226 { 2, 4 },
 227 { 2, 4 },
 228 { 2, 4 },
 229 { 2, 4 },
 230 { 2, 4 },
 231 { 2, 4 },
 232 { 3, 4 },
 233 { 3, 4 },
 234 { 3, 4 },
 235 { 3, 4 },
 236 { 3, 4 },
 237 { 3, 4 },
 238 { 3, 4 },
 239 { 3, 4 },
 240 { 3, 4 },
 241 { 3, 4 },
 242 { 3, 4 },
 243 { 3, 4 },
 244 { 3, 4 },
 245 { 3, 4 },
 246 { 3, 4 },
 247 { 3, 4 },
 248 { 128, 5 },
 249 { 128, 5 },
 250 { 128, 5 },
 251 { 128, 5 },
 252 { 128, 5 },
 253 { 128, 5 },
 254 { 128, 5 },
 255 { 128, 5 },
 256 { 8, 5 },
 257 { 8, 5 },
 258 { 8, 5 },
 259 { 8, 5 },
 260 { 8, 5 },
 261 { 8, 5 },
 262 { 8, 5 },
 263 { 8, 5 },
 264 { 9, 5 },
 265 { 9, 5 },
 266 { 9, 5 },
 267 { 9, 5 },
 268 { 9, 5 },
 269 { 9, 5 },
 270 { 9, 5 },
 271 { 9, 5 },
 272 { 16, 6 },
 273 { 16, 6 },
 274 { 16, 6 },
 275 { 16, 6 },
 276 { 17, 6 },
 277 { 17, 6 },
 278 { 17, 6 },
 279 { 17, 6 },
 280 { 4, 4 },
 281 { 4, 4 },
 282 { 4, 4 },
 283 { 4, 4 },
 284 { 4, 4 },
 285 { 4, 4 },
 286 { 4, 4 },
 287 { 4, 4 },
 288 { 4, 4 },
 289 { 4, 4 },
 290 { 4, 4 },
 291 { 4, 4 },
 292 { 4, 4 },
 293 { 4, 4 },
 294 { 4, 4 },
 295 { 4, 4 },
 296 { 5, 4 },
 297 { 5, 4 },
 298 { 5, 4 },
 299 { 5, 4 },
 300 { 5, 4 },
 301 { 5, 4 },
 302 { 5, 4 },
 303 { 5, 4 },
 304 { 5, 4 },
 305 { 5, 4 },
 306 { 5, 4 },
 307 { 5, 4 },
 308 { 5, 4 },
 309 { 5, 4 },
 310 { 5, 4 },
 311 { 5, 4 },
 312 { 14, 6 },
 313 { 14, 6 },
 314 { 14, 6 },
 315 { 14, 6 },
 316 { 15, 6 },
 317 { 15, 6 },
 318 { 15, 6 },
 319 { 15, 6 },
 320 { 64, 5 },
 321 { 64, 5 },
 322 { 64, 5 },
 323 { 64, 5 },
 324 { 64, 5 },
 325 { 64, 5 },
 326 { 64, 5 },
 327 { 64, 5 },
 328 { 6, 4 },
 329 { 6, 4 },
 330 { 6, 4 },
 331 { 6, 4 },
 332 { 6, 4 },
 333 { 6, 4 },
 334 { 6, 4 },
 335 { 6, 4 },
 336 { 6, 4 },
 337 { 6, 4 },
 338 { 6, 4 },
 339 { 6, 4 },
 340 { 6, 4 },
 341 { 6, 4 },
 342 { 6, 4 },
 343 { 6, 4 },
 344 { 7, 4 },
 345 { 7, 4 },
 346 { 7, 4 },
 347 { 7, 4 },
 348 { 7, 4 },
 349 { 7, 4 },
 350 { 7, 4 },
 351 { 7, 4 },
 352 { 7, 4 },
 353 { 7, 4 },
 354 { 7, 4 },
 355 { 7, 4 },
 356 { 7, 4 },
 357 { 7, 4 },
 358 { 7, 4 },
 359 { 7, 4 },
 360 { -2, 3 },
 361 { -2, 3 },
 362 { -1, 0 },
 363 { -1, 0 },
 364 { -1, 0 },
 365 { -1, 0 },
 366 { -1, 0 },
 367 { -1, 0 },
 368 { -1, 0 },
 369 { -1, 0 },
 370 { -1, 0 },
 371 { -1, 0 },
 372 { -1, 0 },
 373 { -1, 0 },
 374 { -1, 0 },
 375 { -3, 4 },
 376 { 1792, 3 },
 377 { 1792, 3 },
 378 { 1984, 4 },
 379 { 2048, 4 },
 380 { 2112, 4 },
 381 { 2176, 4 },
 382 { 2240, 4 },
 383 { 2304, 4 },
 384 { 1856, 3 },
 385 { 1856, 3 },
 386 { 1920, 3 },
 387 { 1920, 3 },
 388 { 2368, 4 },
 389 { 2432, 4 },
 390 { 2496, 4 },
 391 { 2560, 4 },
 392 { 1472, 1 },
 393 { 1536, 1 },
 394 { 1600, 1 },
 395 { 1728, 1 },
 396 { 704, 1 },
 397 { 768, 1 },
 398 { 832, 1 },
 399 { 896, 1 },
 400 { 960, 1 },
 401 { 1024, 1 },
 402 { 1088, 1 },
 403 { 1152, 1 },
 404 { 1216, 1 },
 405 { 1280, 1 },
 406 { 1344, 1 },
 407 { 1408, 1 }
 408 };
 409
 410 /* black decode table (runlength huffman codes) */
 411 const mmr_table_node jbig2_mmr_black_decode[] = {
 412 { 128, 12 },
 413 { 160, 13 },
 414 { 224, 12 },
 415 { 256, 12 },
 416 { 10, 7 },
 417 { 11, 7 },
 418 { 288, 12 },
 419 { 12, 7 },
 420 { 9, 6 },
 421 { 9, 6 },
 422 { 8, 6 },
 423 { 8, 6 },
 424 { 7, 5 },
 425 { 7, 5 },
 426 { 7, 5 },
 427 { 7, 5 },
 428 { 6, 4 },
 429 { 6, 4 },
 430 { 6, 4 },
 431 { 6, 4 },
 432 { 6, 4 },
 433 { 6, 4 },
 434 { 6, 4 },
 435 { 6, 4 },
 436 { 5, 4 },
 437 { 5, 4 },
 438 { 5, 4 },
 439 { 5, 4 },
 440 { 5, 4 },
 441 { 5, 4 },
 442 { 5, 4 },
 443 { 5, 4 },
 444 { 1, 3 },
 445 { 1, 3 },
 446 { 1, 3 },
 447 { 1, 3 },
 448 { 1, 3 },
 449 { 1, 3 },
 450 { 1, 3 },
 451 { 1, 3 },
 452 { 1, 3 },
 453 { 1, 3 },
 454 { 1, 3 },
 455 { 1, 3 },
 456 { 1, 3 },
 457 { 1, 3 },
 458 { 1, 3 },
 459 { 1, 3 },
 460 { 4, 3 },
 461 { 4, 3 },
 462 { 4, 3 },
 463 { 4, 3 },
 464 { 4, 3 },
 465 { 4, 3 },
 466 { 4, 3 },
 467 { 4, 3 },
 468 { 4, 3 },
 469 { 4, 3 },
 470 { 4, 3 },
 471 { 4, 3 },
 472 { 4, 3 },
 473 { 4, 3 },
 474 { 4, 3 },
 475 { 4, 3 },
 476 { 3, 2 },
 477 { 3, 2 },
 478 { 3, 2 },
 479 { 3, 2 },
 480 { 3, 2 },
 481 { 3, 2 },
 482 { 3, 2 },
 483 { 3, 2 },
 484 { 3, 2 },
 485 { 3, 2 },
 486 { 3, 2 },
 487 { 3, 2 },
 488 { 3, 2 },
 489 { 3, 2 },
 490 { 3, 2 },
 491 { 3, 2 },
 492 { 3, 2 },
 493 { 3, 2 },
 494 { 3, 2 },
 495 { 3, 2 },
 496 { 3, 2 },
 497 { 3, 2 },
 498 { 3, 2 },
 499 { 3, 2 },
 500 { 3, 2 },
 501 { 3, 2 },
 502 { 3, 2 },
 503 { 3, 2 },
 504 { 3, 2 },
 505 { 3, 2 },
 506 { 3, 2 },
 507 { 3, 2 },
 508 { 2, 2 },
 509 { 2, 2 },
 510 { 2, 2 },
 511 { 2, 2 },
 512 { 2, 2 },
 513 { 2, 2 },
 514 { 2, 2 },
 515 { 2, 2 },
 516 { 2, 2 },
 517 { 2, 2 },
 518 { 2, 2 },
 519 { 2, 2 },
 520 { 2, 2 },
 521 { 2, 2 },
 522 { 2, 2 },
 523 { 2, 2 },
 524 { 2, 2 },
 525 { 2, 2 },
 526 { 2, 2 },
 527 { 2, 2 },
 528 { 2, 2 },
 529 { 2, 2 },
 530 { 2, 2 },
 531 { 2, 2 },
 532 { 2, 2 },
 533 { 2, 2 },
 534 { 2, 2 },
 535 { 2, 2 },
 536 { 2, 2 },
 537 { 2, 2 },
 538 { 2, 2 },
 539 { 2, 2 },
 540 { -2, 4 },
 541 { -2, 4 },
 542 { -1, 0 },
 543 { -1, 0 },
 544 { -1, 0 },
 545 { -1, 0 },
 546 { -1, 0 },
 547 { -1, 0 },
 548 { -1, 0 },
 549 { -1, 0 },
 550 { -1, 0 },
 551 { -1, 0 },
 552 { -1, 0 },
 553 { -1, 0 },
 554 { -1, 0 },
 555 { -3, 5 },
 556 { 1792, 4 },
 557 { 1792, 4 },
 558 { 1984, 5 },
 559 { 2048, 5 },
 560 { 2112, 5 },
 561 { 2176, 5 },
 562 { 2240, 5 },
 563 { 2304, 5 },
 564 { 1856, 4 },
 565 { 1856, 4 },
 566 { 1920, 4 },
 567 { 1920, 4 },
 568 { 2368, 5 },
 569 { 2432, 5 },
 570 { 2496, 5 },
 571 { 2560, 5 },
 572 { 18, 3 },
 573 { 18, 3 },
 574 { 18, 3 },
 575 { 18, 3 },
 576 { 18, 3 },
 577 { 18, 3 },
 578 { 18, 3 },
 579 { 18, 3 },
 580 { 52, 5 },
 581 { 52, 5 },
 582 { 640, 6 },
 583 { 704, 6 },
 584 { 768, 6 },
 585 { 832, 6 },
 586 { 55, 5 },
 587 { 55, 5 },
 588 { 56, 5 },
 589 { 56, 5 },
 590 { 1280, 6 },
 591 { 1344, 6 },
 592 { 1408, 6 },
 593 { 1472, 6 },
 594 { 59, 5 },
 595 { 59, 5 },
 596 { 60, 5 },
 597 { 60, 5 },
 598 { 1536, 6 },
 599 { 1600, 6 },
 600 { 24, 4 },
 601 { 24, 4 },
 602 { 24, 4 },
 603 { 24, 4 },
 604 { 25, 4 },
 605 { 25, 4 },
 606 { 25, 4 },
 607 { 25, 4 },
 608 { 1664, 6 },
 609 { 1728, 6 },
 610 { 320, 5 },
 611 { 320, 5 },
 612 { 384, 5 },
 613 { 384, 5 },
 614 { 448, 5 },
 615 { 448, 5 },
 616 { 512, 6 },
 617 { 576, 6 },
 618 { 53, 5 },
 619 { 53, 5 },
 620 { 54, 5 },
 621 { 54, 5 },
 622 { 896, 6 },
 623 { 960, 6 },
 624 { 1024, 6 },
 625 { 1088, 6 },
 626 { 1152, 6 },
 627 { 1216, 6 },
 628 { 64, 3 },
 629 { 64, 3 },
 630 { 64, 3 },
 631 { 64, 3 },
 632 { 64, 3 },
 633 { 64, 3 },
 634 { 64, 3 },
 635 { 64, 3 },
 636 { 13, 1 },
 637 { 13, 1 },
 638 { 13, 1 },
 639 { 13, 1 },
 640 { 13, 1 },
 641 { 13, 1 },
 642 { 13, 1 },
 643 { 13, 1 },
 644 { 13, 1 },
 645 { 13, 1 },
 646 { 13, 1 },
 647 { 13, 1 },
 648 { 13, 1 },
 649 { 13, 1 },
 650 { 13, 1 },
 651 { 13, 1 },
 652 { 23, 4 },
 653 { 23, 4 },
 654 { 50, 5 },
 655 { 51, 5 },
 656 { 44, 5 },
 657 { 45, 5 },
 658 { 46, 5 },
 659 { 47, 5 },
 660 { 57, 5 },
 661 { 58, 5 },
 662 { 61, 5 },
 663 { 256, 5 },
 664 { 16, 3 },
 665 { 16, 3 },
 666 { 16, 3 },
 667 { 16, 3 },
 668 { 17, 3 },
 669 { 17, 3 },
 670 { 17, 3 },
 671 { 17, 3 },
 672 { 48, 5 },
 673 { 49, 5 },
 674 { 62, 5 },
 675 { 63, 5 },
 676 { 30, 5 },
 677 { 31, 5 },
 678 { 32, 5 },
 679 { 33, 5 },
 680 { 40, 5 },
 681 { 41, 5 },
 682 { 22, 4 },
 683 { 22, 4 },
 684 { 14, 1 },
 685 { 14, 1 },
 686 { 14, 1 },
 687 { 14, 1 },
 688 { 14, 1 },
 689 { 14, 1 },
 690 { 14, 1 },
 691 { 14, 1 },
 692 { 14, 1 },
 693 { 14, 1 },
 694 { 14, 1 },
 695 { 14, 1 },
 696 { 14, 1 },
 697 { 14, 1 },
 698 { 14, 1 },
 699 { 14, 1 },
 700 { 15, 2 },
 701 { 15, 2 },
 702 { 15, 2 },
 703 { 15, 2 },
 704 { 15, 2 },
 705 { 15, 2 },
 706 { 15, 2 },
 707 { 15, 2 },
 708 { 128, 5 },
 709 { 192, 5 },
 710 { 26, 5 },
 711 { 27, 5 },
 712 { 28, 5 },
 713 { 29, 5 },
 714 { 19, 4 },
 715 { 19, 4 },
 716 { 20, 4 },
 717 { 20, 4 },
 718 { 34, 5 },
 719 { 35, 5 },
 720 { 36, 5 },
 721 { 37, 5 },
 722 { 38, 5 },
 723 { 39, 5 },
 724 { 21, 4 },
 725 { 21, 4 },
 726 { 42, 5 },
 727 { 43, 5 },
 728 { 0, 3 },
 729 { 0, 3 },
 730 { 0, 3 },
 731 { 0, 3 }
 732 };
 733
 734 #define getbit(buf, x) ( ( buf[x >> 3] >> ( 7 - (x & 7) ) ) & 1 )
 735
 736 static int
 737 jbig2_find_changing_element(const byte *line, int x, int w)
 738 {
 739         int a, b;
 740
 741         if (line == 0)
 742                 return w;
 743
 744         if (x == -1) {
 745                 a = 0;
 746                 x = 0;
 747         }
 748         else {
 749                 a = getbit(line, x);
 750                 x ++;
 751         }
 752
 753         while (x < w) {
 754                 b = getbit(line, x);
 755                 if (a != b)
 756                         break;
 757                 x++;
 758         }
 759
 760         return x;
 761 }
 762
 763 static int
 764 jbig2_find_changing_element_of_color(const byte *line, int x, int w, int color)
 765 {
 766         if (line == 0)
 767                 return w;
 768         x = jbig2_find_changing_element(line, x, w);
 769         if (x < w && getbit(line, x) != color)
 770                 x = jbig2_find_changing_element(line, x, w);
 771         return x;
 772 }
 773
 774 static const byte lm[8] = { 0xFF, 0x7F, 0x3F, 0x1F, 0x0F, 0x07, 0x03, 0x01 };
 775 static const byte rm[8] = { 0x00, 0x80, 0xC0, 0xE0, 0xF0, 0xF8, 0xFC, 0xFE };
 776
 777 static void
 778 jbig2_set_bits(byte *line, int x0, int x1)
 779 {
 780         int a0, a1, b0, b1, a;
 781
 782         a0 = x0 >> 3;
 783         a1 = x1 >> 3;
 784
 785         b0 = x0 & 7;
 786         b1 = x1 & 7;
 787
 788         if (a0 == a1) {
 789                 line[a0] |= lm[b0] & rm[b1];
 790         }
 791         else {
 792                 line[a0] |= lm[b0];
 793                 for (a = a0 + 1; a < a1; a++)
 794                         line[a] = 0xFF;
 795                 if (b1) line[a1] |= rm[b1];
 796         }
 797 }
 798
 799
 800 static int
 801 jbig2_decode_get_code(Jbig2MmrCtx *mmr, const mmr_table_node *table, int initial_bits)
 802 {
 803         uint32_t word = mmr->word;
 804         int table_ix = word >> (32 - initial_bits);
 805         int val = table[table_ix].val;
 806         int n_bits = table[table_ix].n_bits;
 807
 808         if (n_bits > initial_bits) {
 809                 int mask = (1 << (32 - initial_bits)) - 1;
 810                 table_ix = val + ((word & mask) >> (32 - n_bits));
 811                 val = table[table_ix].val;
 812                 n_bits = initial_bits + table[table_ix].n_bits;
 813         }
 814
 815         jbig2_decode_mmr_consume(mmr, n_bits);
 816
 817         return val;
 818 }
 819
 820 static int
 821 jbig2_decode_get_run(Jbig2MmrCtx *mmr, const mmr_table_node *table, int initial_bits)
 822 {
 823         int result = 0;
 824         int val;
 825
 826         do {
 827                 val = jbig2_decode_get_code(mmr, table, initial_bits);
 828                 result += val;
 829         } while (val >= 64);
 830
 831         return result;
 832 }
 833
 834 static int
 835 jbig2_decode_mmr_line(Jbig2MmrCtx *mmr, const byte *ref, byte *dst)
 836 {
 837         int a0 = -1;
 838         int a1, a2, b1, b2;
 839         int c = 0;              /* 0 is white, black is 1 */
 840
 841         while (1)
 842         {
 843                 uint32_t word = mmr->word;
 844                 /* printf ("%08x\n", word); */
 845
 846                 if (a0 >= mmr->width)
 847                         break;
 848
 849                 if ((word >> (32 - 3)) == 1)
 850                 {
 851                         int white_run, black_run;
 852
 853                         jbig2_decode_mmr_consume(mmr, 3);
 854
 855                         if (a0 == -1)
 856                                 a0 = 0;
 857
 858                         if (c == 0) {
 859                                 white_run = jbig2_decode_get_run(mmr, jbig2_mmr_white_decode, 8);
 860                                 black_run = jbig2_decode_get_run(mmr, jbig2_mmr_black_decode, 7);
 861                                 a1 = a0 + white_run;
 862                                 a2 = a1 + black_run;
 863                                 if (a1 > mmr->width) a1 = mmr->width;
 864                                 if (a2 > mmr->width) a2 = mmr->width;
 865                                 if (a2 < a1 || a1 < 0) return -1;
 866                                 jbig2_set_bits(dst, a1, a2);
 867                                 a0 = a2;
 868                                 /* printf ("H %d %d\n", white_run, black_run); */
 869                         }
 870                         else
 871                         {
 872                                 black_run = jbig2_decode_get_run(mmr, jbig2_mmr_black_decode, 7);
 873                                 white_run = jbig2_decode_get_run(mmr, jbig2_mmr_white_decode, 8);
 874                                 a1 = a0 + black_run;
 875                                 a2 = a1 + white_run;
 876                                 if (a1 > mmr->width) a1 = mmr->width;
 877                                 if (a2 > mmr->width) a2 = mmr->width;
 878                                 if (a1 < a0 || a0 < 0) return -1;
 879                                 jbig2_set_bits(dst, a0, a1);
 880                                 a0 = a2;
 881                                 /* printf ("H %d %d\n", black_run, white_run); */
 882                         }
 883                 }
 884
 885                 else if ((word >> (32 - 4)) == 1)
 886                 {
 887                         /* printf ("P\n"); */
 888                         jbig2_decode_mmr_consume(mmr, 4);
 889                         b1 = jbig2_find_changing_element_of_color(ref, a0, mmr->width, !c);
 890                         b2 = jbig2_find_changing_element(ref, b1, mmr->width);
 891                         if (c)
 892                         {
 893                                 if (b2 < a0 || a0 < 0) return -1;
 894                                 jbig2_set_bits(dst, a0, b2);
 895                         }
 896                         a0 = b2;
 897                 }
 898
 899                 else if ((word >> (32 - 1)) == 1)
 900                 {
 901                         /* printf ("V(0)\n"); */
 902                         jbig2_decode_mmr_consume(mmr, 1);
 903                         b1 = jbig2_find_changing_element_of_color(ref, a0, mmr->width, !c);
 904                         if (c)
 905                         {
 906                                 if (b1 < a0 || a0 < 0) return -1;
 907                                 jbig2_set_bits(dst, a0, b1);
 908                         }
 909                         a0 = b1;
 910                         c = !c;
 911                 }
 912
 913                 else if ((word >> (32 - 3)) == 3)
 914                 {
 915                         /* printf ("VR(1)\n"); */
 916                         jbig2_decode_mmr_consume(mmr, 3);
 917                         b1 = jbig2_find_changing_element_of_color(ref, a0, mmr->width, !c);
 918                         if (b1 + 1 > mmr->width) break;
 919                         if (c)
 920                         {
 921                                 if (b1 + 1 < a0 || a0 < 0) return -1;
 922                                 jbig2_set_bits(dst, a0, b1 + 1);
 923                         }
 924                         a0 = b1 + 1;
 925                         c = !c;
 926                 }
 927
 928                 else if ((word >> (32 - 6)) == 3)
 929                 {
 930                         /* printf ("VR(2)\n"); */
 931                         jbig2_decode_mmr_consume(mmr, 6);
 932                         b1 = jbig2_find_changing_element_of_color(ref, a0, mmr->width, !c);
 933                         if (b1 + 2 > mmr->width) break;
 934                         if (c)
 935                         {
 936                                 if (b1 + 2 < a0 || a0 < 0) return -1;
 937                                 jbig2_set_bits(dst, a0, b1 + 2);
 938                         }
 939                         a0 = b1 + 2;
 940                         c = !c;
 941                 }
 942
 943                 else if ((word >> (32 - 7)) == 3)
 944                 {
 945                         /* printf ("VR(3)\n"); */
 946                         jbig2_decode_mmr_consume(mmr, 7);
 947                         b1 = jbig2_find_changing_element_of_color(ref, a0, mmr->width, !c);
 948                         if (b1 + 3 > mmr->width) break;
 949                         if (c)
 950                         {
 951                                 if (b1 + 3 < a0 || a0 < 0) return -1;
 952                                 jbig2_set_bits(dst, a0, b1 + 3);
 953                         }
 954                         a0 = b1 + 3;
 955                         c = !c;
 956                 }
 957
 958                 else if ((word >> (32 - 3)) == 2)
 959                 {
 960                         /* printf ("VL(1)\n"); */
 961                         jbig2_decode_mmr_consume(mmr, 3);
 962                         b1 = jbig2_find_changing_element_of_color(ref, a0, mmr->width, !c);
 963                         if (b1 - 1 < 0) break;
 964                         if (c)
 965                         {
 966                                 if (b1 - 1 < a0 || a0 < 0) return -1;
 967                                 jbig2_set_bits(dst, a0, b1 - 1);
 968                         }
 969                         a0 = b1 - 1;
 970                         c = !c;
 971                 }
 972
 973                 else if ((word >> (32 - 6)) == 2)
 974                 {
 975                         /* printf ("VL(2)\n"); */
 976                         jbig2_decode_mmr_consume(mmr, 6);
 977                         b1 = jbig2_find_changing_element_of_color(ref, a0, mmr->width, !c);
 978                         if (b1 - 2 < 0) break;
 979                         if (c)
 980                         {
 981                                 if (b1 - 2 < a0 || a0 < 0) return -1;
 982                                 jbig2_set_bits(dst, a0, b1 - 2);
 983                         }
 984                         a0 = b1 - 2;
 985                         c = !c;
 986                 }
 987
 988                 else if ((word >> (32 - 7)) == 2)
 989                 {
 990                         /* printf ("VL(3)\n"); */
 991                         jbig2_decode_mmr_consume(mmr, 7);
 992                         b1 = jbig2_find_changing_element_of_color(ref, a0, mmr->width, !c);
 993                         if (b1 - 3 < 0) break;
 994                         if (c)
 995                         {
 996                                 if (b1 - 3 < a0 || a0 < 0) return -1;
 997                                 jbig2_set_bits(dst, a0, b1 - 3);
 998                         }
 999                         a0 = b1 - 3;
1000                         c = !c;
1001                 }
1002
1003                 else
1004                         break;
1005         }
1006
1007         return 0;
1008 }
1009
1010 int
1011 jbig2_decode_generic_mmr(Jbig2Ctx *ctx,
1012         Jbig2Segment *segment,
1013         const Jbig2GenericRegionParams *params,
1014         const byte *data, size_t size,
1015         Jbig2Image *image)
1016 {
1017         Jbig2MmrCtx mmr;
1018         const int rowstride = image->stride;
1019         byte *dst = image->data;
1020         byte *ref = NULL;
1021         int y;
1022         int code = 0;
1023
1024         jbig2_decode_mmr_init(&mmr, image->width, image->height, data, size);
1025
1026         for (y = 0; y < image->height; y++) {
1027                 memset(dst, 0, rowstride);
1028                 code = jbig2_decode_mmr_line(&mmr, ref, dst);
1029                 if (code < 0) return code;
1030                 ref = dst;
1031                 dst += rowstride;
1032         }
1033
1034         return code;
1035 }
1036
1037 /**
1038  * jbig2_decode_halftone_mmr: decode mmr region inside of halftones
1039  *
1040  * @ctx: jbig2 decoder context
1041  * @params: parameters for decoding
1042  * @data: pointer to text region data to be decoded
1043  * @size: length of text region data
1044  * @image: return of decoded image
1045  * @consumed_bytes: return of consumed bytes from @data
1046  *
1047  * MMR decoding that consumes EOFB and returns consumed bytes (@consumed_bytes)
1048  *
1049  * returns: 0
1050  **/
1051 int
1052 jbig2_decode_halftone_mmr(Jbig2Ctx *ctx,
1053         const Jbig2GenericRegionParams *params,
1054         const byte *data, size_t size,
1055         Jbig2Image *image, size_t* consumed_bytes)
1056 {
1057         Jbig2MmrCtx mmr;
1058         const int rowstride = image->stride;
1059         byte *dst = image->data;
1060         byte *ref = NULL;
1061         int y;
1062         int code = 0;
1063         const uint32_t EOFB = 0x001001;
1064
1065         jbig2_decode_mmr_init(&mmr, image->width, image->height, data, size);
1066
1067         for (y = 0; y < image->height; y++) {
1068                 memset(dst, 0, rowstride);
1069                 code = jbig2_decode_mmr_line(&mmr, ref, dst);
1070                if (code < 0) return code;
1071                 ref = dst;
1072                 dst += rowstride;
1073         }
1074
1075         /* test for EOFB (see section 6.2.6) */
1076         if (mmr.word >> 8 == EOFB) {
1077                 mmr.data_index += 3;
1078         }
1079
1080         *consumed_bytes += mmr.data_index + (mmr.bit_index >> 3) +
1081                        (mmr.bit_index > 0 ? 1 : 0);
1082         return code;
1083 }