jbig2arith.cc

// Copyright 2006 Google Inc. All Rights Reserved.
// Author: agl@imperialviolet.org (Adam Langley)
//
// Copyright (C) 2006 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "jbig2arith.h"

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define u64 uint64_t
#define u32 uint32_t
#define u16 uint16_t
#define u8  uint8_t

// C++ doesn't have C99 restricted pointers, but GCC does allow __restrict__
#if !defined(WIN32)
#define restrict __restrict__
#else
#define restrict
#endif

// -----------------------------------------------------------------------------
// This the structure for a single state of the adaptive arithmetic compressor
// -----------------------------------------------------------------------------
struct context {
  u16 qe;
  u8 mps, lps;
};

// -----------------------------------------------------------------------------
// And this is the table of states for that adaptive compressor
// -----------------------------------------------------------------------------
struct context ctbl[] = {
  // This is the standard state table from
  // Table E.1 of the standard. The switch has been omitted and
  // those states are included below
#define STATETABLE \
  {0x5601, F( 1), SWITCH(F( 1))},\
  {0x3401, F( 2), F( 6)},\
  {0x1801, F( 3), F( 9)},\
  {0x0ac1, F( 4), F(12)},\
  {0x0521, F( 5), F(29)},\
  {0x0221, F(38), F(33)},\
  {0x5601, F( 7), SWITCH(F( 6))},\
  {0x5401, F( 8), F(14)},\
  {0x4801, F( 9), F(14)},\
  {0x3801, F(10), F(14)},\
  {0x3001, F(11), F(17)},\
  {0x2401, F(12), F(18)},\
  {0x1c01, F(13), F(20)},\
  {0x1601, F(29), F(21)},\
  {0x5601, F(15), SWITCH(F(14))},\
  {0x5401, F(16), F(14)},\
  {0x5101, F(17), F(15)},\
  {0x4801, F(18), F(16)},\
  {0x3801, F(19), F(17)},\
  {0x3401, F(20), F(18)},\
  {0x3001, F(21), F(19)},\
  {0x2801, F(22), F(19)},\
  {0x2401, F(23), F(20)},\
  {0x2201, F(24), F(21)},\
  {0x1c01, F(25), F(22)},\
  {0x1801, F(26), F(23)},\
  {0x1601, F(27), F(24)},\
  {0x1401, F(28), F(25)},\
  {0x1201, F(29), F(26)},\
  {0x1101, F(30), F(27)},\
  {0x0ac1, F(31), F(28)},\
  {0x09c1, F(32), F(29)},\
  {0x08a1, F(33), F(30)},\
  {0x0521, F(34), F(31)},\
  {0x0441, F(35), F(32)},\
  {0x02a1, F(36), F(33)},\
  {0x0221, F(37), F(34)},\
  {0x0141, F(38), F(35)},\
  {0x0111, F(39), F(36)},\
  {0x0085, F(40), F(37)},\
  {0x0049, F(41), F(38)},\
  {0x0025, F(42), F(39)},\
  {0x0015, F(43), F(40)},\
  {0x0009, F(44), F(41)},\
  {0x0005, F(45), F(42)},\
  {0x0001, F(45), F(43)},
#undef F
#define F(x) x
#define SWITCH(x) (x + 46)
  STATETABLE
#undef SWITCH
#undef F

#define F(x) (x + 46)
#define SWITCH(x) ((x) - 46)
  STATETABLE
#undef SWITCH
#undef F
};

#if __GNUC__ >= 4
#define BRANCH_OPT
#endif

// GCC peephole optimisations
#ifdef BRANCH_OPT
#define likely(x)       __builtin_expect((x),1)
#define unlikely(x)     __builtin_expect((x),0)
#else
#define likely(x)       x
#define unlikely(x)     x
#endif

// see comments in .h file
void
jbig2enc_init(struct jbig2enc_ctx *ctx) {
  memset(ctx->context, 0, JBIG2_MAX_CTX);
  memset(ctx->intctx, 0, 13 * 512);
  ctx->a = 0x8000;
  ctx->c = 0;
  ctx->ct = 12;
  ctx->bp = -1;
  ctx->b = 0;
  ctx->outbuf_used = 0;
  ctx->outbuf = (u8 *) malloc(JBIG2_OUTPUTBUFFER_SIZE);
  ctx->output_chunks = new std::vector<uint8_t *>;
  ctx->iaidctx = NULL;
}

// see comments in .h file
void
jbig2enc_reset(struct jbig2enc_ctx *ctx) {
  ctx->a = 0x8000;
  ctx->c = 0;
  ctx->ct = 12;
  ctx->bp = -1;
  ctx->b = 0;
  free(ctx->iaidctx);
  ctx->iaidctx = NULL;
  memset(ctx->context, 0, JBIG2_MAX_CTX);
  memset(ctx->intctx, 0, 13 * 512);
}

// see comments in .h file
void
jbig2enc_flush(struct jbig2enc_ctx *ctx) {
  ctx->outbuf_used = 0;

  for (std::vector<uint8_t *>::iterator i = ctx->output_chunks->begin();
       i != ctx->output_chunks->end(); ++i) {
    free(*i);
  }
  ctx->output_chunks->clear();
  ctx->bp = -1;
}

// see comments in .h file
void
jbig2enc_dealloc(struct jbig2enc_ctx *ctx) {
  for (std::vector<uint8_t *>::iterator i = ctx->output_chunks->begin();
       i != ctx->output_chunks->end(); ++i) {
    free(*i);
  }
  delete ctx->output_chunks;
  free(ctx->outbuf);
  free(ctx->iaidctx);
}

// -----------------------------------------------------------------------------
// Emit a byte from the compressor by appending to the current output buffer.
// If the buffer is full, allocate a new one
// -----------------------------------------------------------------------------
static void inline
emit(struct jbig2enc_ctx *restrict ctx) {
  if (unlikely(ctx->outbuf_used == JBIG2_OUTPUTBUFFER_SIZE)) {
    ctx->output_chunks->push_back(ctx->outbuf);
    ctx->outbuf = (u8 *) malloc(JBIG2_OUTPUTBUFFER_SIZE);
    ctx->outbuf_used = 0;
  }

  ctx->outbuf[ctx->outbuf_used++] = ctx->b;
}

// -----------------------------------------------------------------------------
// The BYTEOUT procedure from the standard
// -----------------------------------------------------------------------------
static void
byteout(struct jbig2enc_ctx *restrict ctx) {
  if (ctx->b == 0xff) goto rblock;

  if (ctx->c < 0x8000000) goto lblock;
  ctx->b += 1;
  if (ctx->b != 0xff) goto lblock;
  ctx->c &= 0x7ffffff;

rblock:
  if (ctx->bp >= 0) {
#ifdef TRACE
    printf("emit %x\n", ctx->b);
#endif
    emit(ctx);
  }
  ctx->b = ctx->c >> 20;
  ctx->bp++;
  ctx->c &= 0xfffff;
  ctx->ct = 7;
  return;

lblock:
  if (ctx->bp >= 0) {
#ifdef TRACE
    printf("emit %x\n", ctx->b);
#endif
    emit(ctx);
  }
  ctx->b = ctx->c >> 19;
  ctx->bp++;
  ctx->c &= 0x7ffff;
  ctx->ct = 8;
  return;
}

// -----------------------------------------------------------------------------
// A merging of the ENCODE, CODELPS and CODEMPS procedures from the standard
// -----------------------------------------------------------------------------
static void
encode_bit(struct jbig2enc_ctx *restrict ctx, u8 *restrict context, u32 ctxnum, u8 d) {
  const u8 i = context[ctxnum];
  const u8 mps = i > 46 ? 1 : 0;
  const u16 qe = ctbl[i].qe;

#ifdef CODER_DEBUGGING
    fprintf(stderr, "B: %d %d %d %d\n", ctxnum, qe, ctx->a, d);
#endif

#ifdef TRACE
  static int ec = 0;
  printf("%d\t%d %d %x %x %x %d %x %d\n", ec++, i, mps, qe, ctx->a, ctx->c, ctx->ct, ctx->b, ctx->bp);
#endif

  if (unlikely(d != mps)) goto codelps;
#ifdef SURPRISE_MAP
  {
  u8 b = static_cast<unsigned char>
    (((static_cast<float>(qe) / 0xac02) * 255));
  write(3, &b, 1);
  }
#endif
  ctx->a -= qe;
  if (unlikely((ctx->a & 0x8000) == 0)) {
    if (unlikely(ctx->a < qe)) {
      ctx->a = qe;
    } else {
      ctx->c += qe;
    }
    context[ctxnum] = ctbl[i].mps;
    goto renorme;
  } else {
    ctx->c += qe;
  }

  return;

codelps:
#ifdef SURPRISE_MAP
  {
  u8 b = static_cast<unsigned char>
    ((1.0f - (static_cast<float>(qe) / 0xac02)) * 255);
  write(3, &b, 1);
  }
#endif
  ctx->a -= qe;
  if (ctx->a < qe) {
    ctx->c += qe;
  } else {
    ctx->a = qe;
  }
  context[ctxnum] = ctbl[i].lps;

renorme:
  do {
    ctx->a <<= 1;
    ctx->c <<= 1;
    ctx->ct -= 1;
    if (unlikely(!ctx->ct)) {
      byteout(ctx);
    }
  } while ((ctx->a & 0x8000) == 0);
}

// -----------------------------------------------------------------------------
// The FINALISE procudure from the standard
// -----------------------------------------------------------------------------
static void
encode_final(struct jbig2enc_ctx *restrict ctx) {
  // SETBITS
  const u32 tempc = ctx->c + ctx->a;
  ctx->c |= 0xffff;
  if (ctx->c >= tempc) {
    ctx->c -= 0x8000;
  }

  ctx->c <<= ctx->ct;
  byteout(ctx);
  ctx->c <<= ctx->ct;
  byteout(ctx);
  emit(ctx);
  if (ctx->b != 0xff) {
#ifdef TRACE
    printf("emit 0xff\n");
#endif
    ctx->b = 0xff;
    emit(ctx);
  }
#ifdef TRACE
  printf("emit 0xac\n");
#endif
  ctx->b = 0xac;
  emit(ctx);
}

// see comments in .h file
void
jbig2enc_final(struct jbig2enc_ctx *restrict ctx) {
  encode_final(ctx);
}

// -----------------------------------------------------------------------------
// When encoding integers there are a number of different cases. This structure
// contains all the information for one of those cases
// -----------------------------------------------------------------------------
struct intencrange_s {
  int bot, top;  // the range of numbers for which this is valid
  u8 data, bits; // the bits of data to write first, and the number which are valid
                 // These bits are taken from the bottom of the u8, in reverse order
  u16 delta;     // the amount to subtract from the value before encoding it
  u8 intbits;    // number of bits to use to encode the integer
};

// table for how to encode integers of a given range
static struct intencrange_s intencrange[] = {
  {0,   3,  0, 2, 0, 2},
  {-1, -1,  9, 4, 0, 0},
  {-3, -2,  5, 3, 2, 1},
  {4,  19,  2, 3, 4, 4},
  {-19,-4,  3, 3, 4, 4},
  {20, 83,  6, 4, 20, 6},
  {-83,-20, 7, 4, 20, 6},
  {84, 339, 14,5, 84, 8},
  {-339,-84,15,5, 84, 8},
  {340,4435,30,6, 340, 12},
  {-4435,-340,31,6,340, 12},
  {4436,2000000000,62,6,4436, 32},
  {-2000000000,-4436,63,6,4436, 32}
};

// see comments in .h file
void
jbig2enc_oob(struct jbig2enc_ctx *restrict ctx, int proc) {
  u8 *const context = ctx->intctx[proc];

  encode_bit(ctx, context, 1, 1);
  encode_bit(ctx, context, 3, 0);
  encode_bit(ctx, context, 6, 0);
  encode_bit(ctx, context, 12, 0);
}

// see comments in .h file
void
jbig2enc_int(struct jbig2enc_ctx *restrict ctx, int proc, int value) {
  u8 *const context = ctx->intctx[proc];
  int i;

  if (value > 2000000000 || value < -2000000000) abort();

  u32 prev = 1;

  for (i = 0; ; ++i) {
    if (intencrange[i].bot <= value && intencrange[i].top >= value) break;
  }
  if (value < 0) value = -value;
  value -= intencrange[i].delta;

  u8 data = intencrange[i].data;
  for (int j = 0; j < intencrange[i].bits; ++j) {
    const u8 v = data & 1;
    encode_bit(ctx, context, prev, v);
    data >>= 1;
    if (prev & 0x100) {
      // prev > 256
      prev = (((prev << 1) | v) & 0x1ff) | 0x100;
    } else {
      prev = (prev << 1) | v;
    }
  }

  // move the data in value to the top of the word
  value <<= (32 - intencrange[i].intbits);
  for (int j = 0; j < intencrange[i].intbits; ++j) {
    const u8 v = (value & 0x80000000) >> 31;
    encode_bit(ctx, context, prev, v);
    // roll the next bit into place
    value <<= 1;
    if (prev & 0x100) {
      // prev > 256
      prev = (((prev << 1) | v) & 0x1ff) | 0x100;
    } else {
      prev = (prev << 1) | v;
    }
  }
}

// see comments in .h file
void
jbig2enc_iaid(struct jbig2enc_ctx *restrict ctx, int symcodelen, int value) {
  if (!ctx->iaidctx) {
    // we've not yet allocated the context index buffer for this
    ctx->iaidctx = (u8 *) malloc(1 << symcodelen);
    memset(ctx->iaidctx, 0, 1 << symcodelen);
  }
  const u32 mask = (1 << (symcodelen + 1)) - 1;

  value <<= (32 - symcodelen);  // roll the data to the top of the word
  u32 prev = 1;
  for (int i = 0; i < symcodelen; ++i) {
    const u32 tval = prev & mask;
    const u8 v = (value & 0x80000000) >> 31;
    encode_bit(ctx, ctx->iaidctx, tval, v);
    prev = (prev << 1) | v;
    value <<= 1;
  }
}

// This is the test input to the coder as given in the standard (H.2)
static const u8 input[] = { 0, 2, 0, 0x51, 0, 0, 0, 0xc0, 0x03, 0x52, 0x87,
  0x2a, 0xaa, 0xaa, 0xaa, 0xaa, 0x82, 0xc0, 0x20, 0, 0xfc, 0xd7, 0x9e, 0xf6,
  0xbf, 0x7f, 0xed, 0x90, 0x4f, 0x46, 0xa3, 0xbf } ;

// -----------------------------------------------------------------------------
// This function  is used by jbig2enc_image to fetch values from the image and
// to automatically extend the range of the image on three sides with zero's
// -----------------------------------------------------------------------------
static u8 image_get(const u8 *restrict image, int x, int y, int mx, int my) {
  if (y < 0) return 0;
  if (x >= mx) return 0;
  if (y >= my) return 0;
  return image[mx * y + x];
}

// see comments in .h file
unsigned
jbig2enc_datasize(const struct jbig2enc_ctx *ctx) {
  return JBIG2_OUTPUTBUFFER_SIZE * ctx->output_chunks->size() + ctx->outbuf_used;
}

// see comments in .h file
void
jbig2enc_tobuffer(const struct jbig2enc_ctx *restrict ctx, u8 *restrict buffer) {
  int j = 0;
  for (std::vector<u8 *>::const_iterator i = ctx->output_chunks->begin();
       i != ctx->output_chunks->end(); ++i) {
    memcpy(&buffer[j], *i, JBIG2_OUTPUTBUFFER_SIZE);
    j += JBIG2_OUTPUTBUFFER_SIZE;
  }

  memcpy(&buffer[j], ctx->outbuf, ctx->outbuf_used);
}

// This is the context used for the TPGD bits
#define TPGDCTX 0x9b25

// -----------------------------------------------------------------------------
// This is designed for Leptonica's 1bpp packed format images. Each row is some
// number of 32-bit words. Pixels are in native-byte-order in each word.
// -----------------------------------------------------------------------------
void
jbig2enc_bitimage(struct jbig2enc_ctx *restrict ctx, const u8 *restrict idata,
                  int mx, int my, bool duplicate_line_removal) {
  const u32 *restrict data = (u32 *) idata;
  u8 *const context = ctx->context;
  const unsigned words_per_row = (mx + 31) / 32;
  const unsigned bytes_per_row = words_per_row * 4;

  u8 ltp = 0, sltp = 0;

  for (int y = 0; y < my; ++y) {
    int x = 0;

    // the c* values store the context bits for each row. The template is fixed
    // as template 0 with the floating bits in the default locations.
    u16 c1, c2, c3;
    // the w* values contain words from each of the rows: w1 is from two rows
    // up etc. The next bit to roll onto the context values are kept at the top
    // of these words.
    u32 w1, w2, w3;
    w1 = w2 = w3 = 0;

    if (y >= 2) w1 = data[(y - 2) * words_per_row];
    if (y >= 1) {
      w2 = data[(y - 1) * words_per_row];

      if (duplicate_line_removal) {
        // it's possible that the last row was the same as this row
        if (memcmp(&data[y * words_per_row], &data[(y - 1) * words_per_row],
                   bytes_per_row) == 0) {
          sltp = ltp ^ 1;
          ltp = 1;
        } else {
          sltp = ltp;
          ltp = 0;
        }
      }
    }
    if (duplicate_line_removal) {
      encode_bit(ctx, context, TPGDCTX, sltp);
      if (ltp) continue;
    }
    w3 = data[y * words_per_row];

    // the top three bits are the start of the context c1
    c1 = w1 >> 29;
    c2 = w2 >> 28;
    // and we need to remove the used bits from the w* vars
    w1 <<= 3;
    w2 <<= 4;
    c3 = 0;
    for (x = 0; x < mx; ++x) {
      const u16 tval = (c1 << 11) | (c2 << 4) | c3;
      const u8 v = (w3 & 0x80000000) >> 31;

      //fprintf(stderr, "%d %d %d %d\n", x, y, tval, v);
      encode_bit(ctx, context, tval, v);
      c1 <<= 1;
      c2 <<= 1;
      c3 <<= 1;
      c1 |= (w1 & 0x80000000) >> 31;
      c2 |= (w2 & 0x80000000) >> 31;
      c3 |= v;
      const int m = x % 32;
      if (m == 28 && y >= 2) {
        // need to roll in another word from two lines up
        const unsigned wordno = (x / 32) + 1;
        if (wordno >= words_per_row) {
          w1 = 0;
        } else {
          w1 = data[(y - 2) * words_per_row + wordno];
        }
      } else {
        w1 <<= 1;
      }

      if (m == 27 && y >= 1) {
        // need to roll in another word from the last line
        const unsigned wordno = (x / 32) + 1;
        if (wordno >= words_per_row) {
          w2 = 0;
        } else {
          w2 = data[(y - 1) * words_per_row + wordno];
        }
      } else {
        w2 <<= 1;
      }

      if (m == 31) {
        // need to roll in another word from this line
        const unsigned wordno = (x / 32) + 1;
        if (wordno >= words_per_row) {
          w3 = 0;
        } else {
          w3 = data[y * words_per_row + wordno];
        }
      } else {
        w3 <<= 1;
      }

      c1 &= 31;
      c2 &= 127;
      c3 &= 15;
    }
  }
}

void
jbig2enc_refine(struct jbig2enc_ctx *__restrict__ ctx,
                const uint8_t *__restrict__ itempl, int tx, int ty,
                const uint8_t *__restrict__ itarget, int mx, int my,
                int ox, int oy) {
  const u32 *restrict templdata = (u32 *) itempl;
  const u32 *restrict data = (u32 *) itarget;
  u8 *restrict const context = ctx->context;

  static int image_counter = 0;

  image_counter++;

#ifdef SYM_DEBUGGING
  fprintf(stderr, "refine:%d %d %d %d\n", tx, ty, mx, my);
#endif

  const unsigned templwords_per_row = (tx + 31) / 32;
  const unsigned words_per_row = (mx + 31) / 32;

  for (int y = 0; y < my; ++y) {
    int x;
    const int temply = y + oy;
    // the template is fixed to the 13 pixel template with the floating bits in
    // the default locations.
    // we have 5 words of context. The first three are the last, current and
    // next rows of the template. The last two are the last and current rows of
    // the target.
    // To form the 14 bits of content these are packed from the least
    // significant bits rightward.
    u16 c1, c2, c3, c4, c5;
    // the w* values contain words from each of the corresponding rows. The
    // next bit to be part of the context is kept at the top of these words
    u32 w1, w2, w3, w4, w5;
    w1 = w2 = w3 = w4 = w5 = 0;

    if (temply >= 1 && (temply - 1) < ty) w1 = templdata[(temply - 1) * templwords_per_row];
    if (temply >= 0 && temply < ty) w2 = templdata[temply * templwords_per_row];
    if (temply >= -1 && temply + 1 < ty) w3 = templdata[(temply + 1) * templwords_per_row];

    // the x offset prevents a hassel because we are dealing with bits. Thus we
    // restrict it to being {-1, 0, 1}.
    if (y >= 1) w4 = data[(y - 1) * words_per_row];
    w5 = data[y * words_per_row];

    const int shiftoffset = 30 + ox;
    c1 = w1 >> shiftoffset;
    c2 = w2 >> shiftoffset;
    c3 = w3 >> shiftoffset;

    c4 = w4 >> 30;
    c5 = 0;

    // the w* should contain the next bit to be included in the context, in the
    // MSB position. Thus we need to roll the used bits out of the way.
    const int bits_to_trim = 2 - ox;
    w1 <<= bits_to_trim;
    w2 <<= bits_to_trim;
    w3 <<= bits_to_trim;

    w4 <<= 2;

    for (x = 0; x < mx; ++x) {
      const u16 tval = (c1 << 10) | (c2 << 7) | (c3 << 4) | (c4 << 1) | c5;
      const u8 v = w5 >> 31;

#ifdef SYM_DEBUGGING
      fprintf(stderr, "%d %d %d %d\n", x, y, tval, v);
#endif
      encode_bit(ctx, context, tval, v);
      c1 <<= 1;
      c2 <<= 1;
      c3 <<= 1;
      c4 <<= 1;
      c1 |= w1 >> 31;
      c2 |= w2 >> 31;
      c3 |= w3 >> 31;
      c4 |= w4 >> 31;
      c5 = v;

      const int m = x % 32;
      const unsigned wordno = (x / 32) + 1;
      if (m == 29 + ox) {
        // have run out of bits in the w[123] values. Need to get more.

        if (wordno >= templwords_per_row) {
          w1 = w2 = w3 = 0;
        } else {
          if (temply >= 1 && (temply - 1 < ty)) {
            w1 = templdata[(temply - 1) * templwords_per_row + wordno];
          } else {
            w1 = 0;
          }
          if (temply >= 0 && temply < ty) {
            w2 = templdata[temply * templwords_per_row + wordno];
          } else {
            w2 = 0;
          }
          if (temply >= -1 && (temply + 1) < ty) {
            w3 = templdata[(temply + 1) * templwords_per_row + wordno];
          } else {
            w3 = 0;
          }
        }
      } else {
        w1 <<= 1;
        w2 <<= 1;
        w3 <<= 1;
      }

      if (m == 29 && y >= 1) {
        // run out of data from w4
        if (wordno >= words_per_row) {
          w4 = 0;
        } else {
          w4 = data[(y - 1) * words_per_row + wordno];
        }
      } else {
        w4 <<= 1;
      }

      if (m == 31) {
        // run out of data from w5
        if (wordno >= words_per_row) {
          w5 = 0;
        } else {
          w5 = data[y * words_per_row + wordno];
        }
      } else {
        w5 <<= 1;
      }

      c1 &= 7;
      c2 &= 7;
      c3 &= 7;
      c4 &= 7;
    }
  }
}

// see comments in .h file
void
jbig2enc_image(struct jbig2enc_ctx *restrict ctx, const u8 *restrict data,
               int mx, int my, bool duplicate_line_removal) {
  u8 *const context = ctx->context;
  u8 ltp = 0;
  u8 sltp = 0;
  for (int y = 0; y < my; ++y) {
    int x = 0;
    u16 c1 = (image_get(data, x, y - 2, mx, my) << 2) |
             (image_get(data, x + 1, y - 2, mx, my) << 1) |
             (image_get(data, x + 2, y - 2, mx, my));
    u16 c2 = (image_get(data, x, y - 1, mx, my) << 3) |
             (image_get(data, x + 1, y - 1, mx, my) << 2) |
             (image_get(data, x + 2, y - 1, mx, my) << 1) |
             (image_get(data, x + 3, y - 1, mx, my));
    u16 c3 = 0;
    if (y > 0) {
      // it's possible that the last row was the same as this row
      if (memcmp(&data[y * mx], &data[(y - 1) * mx], mx) == 0) {
        sltp = ltp ^ 1;
        ltp = 1;
      } else {
        sltp = ltp;
        ltp = 0;
      }
    }
    if (duplicate_line_removal) {
      encode_bit(ctx, context, TPGDCTX, sltp);
      if (ltp) continue;
    }
    for (x = 0; x < mx; ++x) {
      const u16 tval = (c1 << 11) | (c2 << 4) | c3;
      const u8 v = image_get(data, x, y, mx, my);
      encode_bit(ctx, context, tval, v);
      c1 <<= 1;
      c2 <<= 1;
      c3 <<= 1;
      c1 |= image_get(data, x + 3, y - 2, mx, my);
      c2 |= image_get(data, x + 4, y - 1, mx, my);
      c3 |= v;
      c1 &= 31;
      c2 &= 127;
      c3 &= 15;
    }
  }
}