//C-  -*- C++ -*-

//C- -------------------------------------------------------------------

//C- DjVuLibre-3.5

//C- Copyright (c) 2002  Leon Bottou and Yann Le Cun.

//C- Copyright (c) 2001  AT&T

//C-

//C- This software is subject to, and may be distributed under, the

//C- GNU General Public License, either Version 2 of the license,

//C- or (at your option) any later version. The license should have

//C- accompanied the software or you may obtain a copy of the license

//C- from the Free Software Foundation at http://www.fsf.org .

//C-

//C- This program is distributed in the hope that it will be useful,

//C- but WITHOUT ANY WARRANTY; without even the implied warranty of

//C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

//C- GNU General Public License for more details.

//C- 

//C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library from

//C- Lizardtech Software.  Lizardtech Software has authorized us to

//C- replace the original DjVu(r) Reference Library notice by the following

//C- text (see doc/lizard2002.djvu and doc/lizardtech2007.djvu):

//C-

//C-  ------------------------------------------------------------------

//C- | DjVu (r) Reference Library (v. 3.5)

//C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.

//C- | The DjVu Reference Library is protected by U.S. Pat. No.

//C- | 6,058,214 and patents pending.

//C- |

//C- | This software is subject to, and may be distributed under, the

//C- | GNU General Public License, either Version 2 of the license,

//C- | or (at your option) any later version. The license should have

//C- | accompanied the software or you may obtain a copy of the license

//C- | from the Free Software Foundation at http://www.fsf.org .

//C- |

//C- | The computer code originally released by LizardTech under this

//C- | license and unmodified by other parties is deemed "the LIZARDTECH

//C- | ORIGINAL CODE."  Subject to any third party intellectual property

//C- | claims, LizardTech grants recipient a worldwide, royalty-free, 

//C- | non-exclusive license to make, use, sell, or otherwise dispose of 

//C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the 

//C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU 

//C- | General Public License.   This grant only confers the right to 

//C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to 

//C- | the extent such infringement is reasonably necessary to enable 

//C- | recipient to make, have made, practice, sell, or otherwise dispose 

//C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to 

//C- | any greater extent that may be necessary to utilize further 

//C- | modifications or combinations.

//C- |

//C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY

//C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED

//C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF

//C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

//C- +------------------------------------------------------------------

#ifdef HAVE_CONFIG_H

# include "config.h"

#endif

#if NEED_GNUG_PRAGMAS

# pragma implementation

#endif

// - Author: Leon Bottou, 07/1998

#include "BSByteStream.h"

#include "GString.h"

#undef BSORT_TIMER

#ifdef BSORT_TIMER

#include "GOS.h"

#endif

#include <stddef.h>

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

#ifdef HAVE_NAMESPACES

namespace DJVU {

# ifdef NOT_DEFINED // Just to fool emacs c++ mode

}

#endif

#endif

// ========================================

// --- Assertion

#define ASSERT(expr) do{if(!(expr))G_THROW("assertion ("#expr") failed");}while(0)

// ========================================

// --- Global Definitions

#ifdef OVERFLOW

#undef OVERFLOW

#endif

// Overflow required when encoding

static const int OVERFLOW=32;

// Sorting tresholds

static const int RANKSORT_THRESH=10;

static const int QUICKSORT_STACK=512;

static const int PRESORT_THRESH=10;

static const int PRESORT_DEPTH=8;

static const int RADIX_THRESH=32768;

static const int FREQS0=100000;

static const int FREQS1=1000000;

// ========================================

// -- Sorting Routines

class _BSort  // DJVU_CLASS

{

public:

  ~_BSort();

  _BSort(unsigned char *data, int size);

  void run(int &markerpos);

private:

  // Members

  int            size;

  unsigned char *data;

  unsigned int  *posn;

  GPBuffer<unsigned int> gposn;

  int           *rank;

  GPBuffer<int> grank;

  // Helpers

  inline int GT(int p1, int p2, int depth);

  inline int GTD(int p1, int p2, int depth);

  // -- final in-depth sort

  void ranksort(int lo, int hi, int d);

  // -- doubling sort

  int  pivot3r(int *rr, int lo, int hi);

  void quicksort3r(int lo, int hi, int d);

  // -- presort to depth PRESORT_DEPTH

  unsigned char pivot3d(unsigned char *dd, int lo, int hi);

  void quicksort3d(int lo, int hi, int d);

  // -- radixsort

  void radixsort16(void);

  void radixsort8(void);

};

// blocksort -- the main entry point

static void 

blocksort(unsigned char *data, int size, int &markerpos)

{

  _BSort bsort(data, size);

  bsort.run(markerpos);

}

// _BSort construction

_BSort::_BSort(unsigned char *xdata, int xsize)

  : size(xsize), data(xdata), gposn(posn,xsize), grank(rank,xsize+1)

{

  ASSERT(size>0 && size<0x1000000);

  rank[size] = -1;

}

_BSort::~_BSort()

{

}

// GT -- compare suffixes using rank information

inline int 

_BSort::GT(int p1, int p2, int depth)

{

  int r1, r2;

  int twod = depth + depth;

  while (1)

    {

      r1=rank[p1+depth]; r2=rank[p2+depth];

      p1+=twod;  p2+=twod;

      if (r1!=r2) 

        return (r1>r2);

      r1=rank[p1]; r2=rank[p2];

      if (r1!=r2) 

        return (r1>r2);

      r1=rank[p1+depth]; r2=rank[p2+depth];

      p1+=twod;  p2+=twod;

      if (r1!=r2) 

        return (r1>r2);

      r1=rank[p1]; r2=rank[p2];

      if (r1!=r2) 

        return (r1>r2);

      r1=rank[p1+depth]; r2=rank[p2+depth];

      p1+=twod;  p2+=twod;

      if (r1!=r2) 

        return (r1>r2);

      r1=rank[p1]; r2=rank[p2];

      if (r1!=r2) 

        return (r1>r2);

      r1=rank[p1+depth]; r2=rank[p2+depth];

      p1+=twod;  p2+=twod;

      if (r1!=r2) 

        return (r1>r2);

      r1=rank[p1]; r2=rank[p2];

      if (r1!=r2) 

        return (r1>r2);

    };

}

// _BSort::ranksort -- 

// -- a simple insertion sort based on GT

void 

_BSort::ranksort(int lo, int hi, int depth)

{

  int i,j;

  for (i=lo+1; i<=hi; i++)

    {

      int tmp = posn[i];

      for(j=i-1; j>=lo && GT(posn[j], tmp, depth); j--)

        posn[j+1] = posn[j];

      posn[j+1] = tmp;

    }

  for(i=lo;i<=hi;i++) 

    rank[posn[i]]=i;

}

// pivot -- return suitable pivot

inline int

_BSort::pivot3r(int *rr, int lo, int hi)

{

  int c1, c2, c3;

  if (hi-lo > 256)

    {

      c1 = pivot3r(rr, lo, (6*lo+2*hi)/8);

      c2 = pivot3r(rr, (5*lo+3*hi)/8, (3*lo+5*hi)/8);

      c3 = pivot3r(rr, (2*lo+6*hi)/8, hi);

    }

  else

    {

      c1 = rr[posn[lo]];

      c2 = rr[posn[(lo+hi)/2]];

      c3 = rr[posn[hi]];

    }

  // Extract median

  if (c1>c3)

    { int tmp=c1; c1=c3; c3=tmp; }

  if (c2<=c1)

    return c1;

  else if (c2>=c3)

    return c3;

  else

    return c2;

}

// _BSort::quicksort3r -- Three way quicksort algorithm 

//    Sort suffixes based on rank at pos+depth

//    The algorithm breaks into ranksort when size is 

//    smaller than RANKSORT_THRESH

static inline int

mini(int a, int b) 

{

  return (a<=b) ? a : b;

}

static inline void

vswap(int i, int j, int n, unsigned int *x)

{

  while (n-- > 0) 

    { int tmp = x[i]; x[i++]=x[j]; x[j++]=tmp; }

}

void 

_BSort::quicksort3r(int lo, int hi, int depth)

{

  /* Initialize stack */

  int slo[QUICKSORT_STACK];

  int shi[QUICKSORT_STACK];

  int sp = 1;

  slo[0] = lo;

  shi[0] = hi;

  // Recursion elimination loop

  while (--sp>=0)

    {

      lo = slo[sp];

      hi = shi[sp];

      // Test for insertion sort

      if (hi-lo

        {

          ranksort(lo, hi, depth);

        }

      else

        {

          int tmp;

          int *rr=rank+depth;

          int med = pivot3r(rr,lo,hi);

          // -- positions are organized as follows:

          //   [lo..l1[ [l1..l[ ]h..h1] ]h1..hi]

          //      =        <       >        =

          int l1 = lo;

          int h1 = hi;

          while (rr[posn[l1]]==med && l1

          while (rr[posn[h1]]==med && l1

          int l = l1;

          int h = h1;

          // -- partition set

          for (;;)

            {

              while (l<=h)

                {

                  int c = rr[posn[l]] - med;

                  if (c > 0) break;

                  if (c == 0) { tmp=posn[l]; posn[l]=posn[l1]; posn[l1++]=tmp; }

                  l++;

                }

              while (l<=h)

                {

                  int c = rr[posn[h]] - med;

                  if (c < 0) break;

                  if (c == 0) { tmp=posn[h]; posn[h]=posn[h1]; posn[h1--]=tmp; }

                  h--;

                }

              if (l>h) break;

              tmp=posn[l]; posn[l]=posn[h]; posn[h]=tmp;

            }

          // -- reorganize as follows

          //   [lo..l1[ [l1..h1] ]h1..hi]

          //      <        =        > 

          tmp = mini(l1-lo, l-l1);

          vswap(lo, l-tmp, tmp, posn);

          l1 = lo + (l-l1);

          tmp = mini(hi-h1, h1-h);

          vswap(hi-tmp+1, h+1, tmp, posn);

          h1 = hi - (h1-h);

          // -- process segments

          ASSERT(sp+2

          // ----- middle segment (=?) [l1, h1]

          for(int i=l1;i<=h1;i++) 

            rank[posn[i]] = h1;

          // ----- lower segment (<) [lo, l1[

          if (l1 > lo)

            {

              for(int i=lo;i

                rank[posn[i]]=l1-1;

              slo[sp]=lo;

              shi[sp]=l1-1;

              if (slo[sp] < shi[sp])  

                sp++;

            }

          // ----- upper segment (>) ]h1, hi]

          if (h1 < hi)

            {

              slo[sp]=h1+1;

              shi[sp]=hi;

              if (slo[sp] < shi[sp])  

                sp++;

            }

        }

    }

}

// GTD -- compare suffixes using data information 

//  (up to depth PRESORT_DEPTH)

inline int 

_BSort::GTD(int p1, int p2, int depth)

{

  unsigned char c1, c2;

  p1+=depth; p2+=depth;

  while (depth < PRESORT_DEPTH)

    {

      // Perform two

      c1=data[p1]; c2=data[p2];

      if (c1!=c2) 

        return (c1>c2);

      c1=data[p1+1]; c2=data[p2+1];

      p1+=2;  p2+=2; depth+=2;

      if (c1!=c2) 

        return (c1>c2);

    }

  if (p1

    return 0;

  return (p1

}

// pivot3d -- return suitable pivot

inline unsigned char

_BSort::pivot3d(unsigned char *rr, int lo, int hi)

{

  unsigned char c1, c2, c3;

  if (hi-lo > 256)

    {

      c1 = pivot3d(rr, lo, (6*lo+2*hi)/8);

      c2 = pivot3d(rr, (5*lo+3*hi)/8, (3*lo+5*hi)/8);

      c3 = pivot3d(rr, (2*lo+6*hi)/8, hi);

    }

  else

    {

      c1 = rr[posn[lo]];

      c2 = rr[posn[(lo+hi)/2]];

      c3 = rr[posn[hi]];

    }

  // Extract median

  if (c1>c3)

    { int tmp=c1; c1=c3; c3=tmp; }

  if (c2<=c1)

    return c1;

  else if (c2>=c3)

    return c3;

  else

    return c2;

}

// _BSort::quicksort3d -- Three way quicksort algorithm 

//    Sort suffixes based on strings until reaching

//    depth rank at pos+depth

//    The algorithm breaks into ranksort when size is 

//    smaller than PRESORT_THRESH

void 

_BSort::quicksort3d(int lo, int hi, int depth)

{

  /* Initialize stack */

  int slo[QUICKSORT_STACK];

  int shi[QUICKSORT_STACK];

  int sd[QUICKSORT_STACK];

  int sp = 1;

  slo[0] = lo;

  shi[0] = hi;

  sd[0] = depth;

  // Recursion elimination loop

  while (--sp>=0)

    {

      lo = slo[sp];

      hi = shi[sp];

      depth = sd[sp];

      // Test for insertion sort

      if (depth >= PRESORT_DEPTH)

        {

          for (int i=lo; i<=hi; i++)

            rank[posn[i]] = hi;

        }

      else if (hi-lo

        {

          int i,j;

          for (i=lo+1; i<=hi; i++)

            {

              int tmp = posn[i];

              for(j=i-1; j>=lo && GTD(posn[j], tmp, depth); j--)

                posn[j+1] = posn[j];

              posn[j+1] = tmp;

            }

          for(i=hi;i>=lo;i=j)

            {

              int tmp = posn[i];

              rank[tmp] = i;

              for (j=i-1; j>=lo && !GTD(tmp,posn[j],depth); j--)

                rank[posn[j]] = i;

            }

        }

        else

        {

          int tmp;

          unsigned char *dd=data+depth;

          unsigned char med = pivot3d(dd,lo,hi);

          // -- positions are organized as follows:

          //   [lo..l1[ [l1..l[ ]h..h1] ]h1..hi]

          //      =        <       >        =

          int l1 = lo;

          int h1 = hi;

          while (dd[posn[l1]]==med && l1

          while (dd[posn[h1]]==med && l1

          int l = l1;

          int h = h1;

          // -- partition set

          for (;;)

            {

              while (l<=h)

                {

                  int c = (int)dd[posn[l]] - (int)med;

                  if (c > 0) break;

                  if (c == 0) { tmp=posn[l]; posn[l]=posn[l1]; posn[l1++]=tmp; }

                  l++;

                }

              while (l<=h)

                {

                  int c = (int)dd[posn[h]] - (int)med;

                  if (c < 0) break;

                  if (c == 0) { tmp=posn[h]; posn[h]=posn[h1]; posn[h1--]=tmp; }

                  h--;

                }

              if (l>h) break;

              tmp=posn[l]; posn[l]=posn[h]; posn[h]=tmp;

            }

          // -- reorganize as follows

          //   [lo..l1[ [l1..h1] ]h1..hi]

          //      <        =        > 

          tmp = mini(l1-lo, l-l1);

          vswap(lo, l-tmp, tmp, posn);

          l1 = lo + (l-l1);

          tmp = mini(hi-h1, h1-h);

          vswap(hi-tmp+1, h+1, tmp, posn);

          h1 = hi - (h1-h);

          // -- process segments

          ASSERT(sp+3

          // ----- middle segment (=?) [l1, h1]

          l = l1; h = h1;

          if (med==0) // special case for marker [slow]

            for (int i=l; i<=h; i++)

              if ((int)posn[i]+depth == size-1)

                { 

                  tmp=posn[i]; posn[i]=posn[l]; posn[l]=tmp; 

                  rank[tmp]=l++; break; 

                }

          if (l

            { slo[sp] = l; shi[sp] = h; sd[sp++] = depth+1; }

          else if (l==h)

            { rank[posn[h]] = h; }

          // ----- lower segment (<) [lo, l1[

          l = lo;

          h = l1-1;

          if (l

            { slo[sp] = l; shi[sp] = h; sd[sp++] = depth; }

          else if (l==h)

            { rank[posn[h]] = h; }

          // ----- upper segment (>) ]h1, hi]

          l = h1+1;

          h = hi;

          if (l

            { slo[sp] = l; shi[sp] = h; sd[sp++] = depth; }

          else if (l==h)

            { rank[posn[h]] = h; }

        }

    }

}

// _BSort::radixsort8 -- 8 bit radix sort

void 

_BSort::radixsort8(void)

{

  int i;

  // Initialize frequency array

  int lo[256], hi[256];

  for (i=0; i<256; i++)

    hi[i] = lo[i] = 0;

  // Count occurences

  for (i=0; i

    hi[data[i]] ++;

  // Compute positions (lo)

  int last = 1;

  for (i=0; i<256; i++)

    {

      lo[i] = last;

      hi[i] = last + hi[i] - 1;

      last = hi[i] + 1;

    }

  for (i=0; i

    {

      posn[ lo[data[i]]++ ] = i;

      rank[ i ] = hi[data[i]];

    }

  // Process marker "$"

  posn[0] = size-1;

  rank[size-1] = 0;

  // Extra element

  rank[size] = -1;

}

// _BSort::radixsort16 -- 16 bit radix sort

void 

_BSort::radixsort16(void)

{

  int i;

  // Initialize frequency array

  int *ftab;

  GPBuffer<int> gftab(ftab,65536);

  for (i=0; i<65536; i++)

    ftab[i] = 0;

  // Count occurences

  unsigned char c1 = data[0];

  for (i=0; i

    {

      unsigned char c2 = data[i+1];

      ftab[(c1<<8)|c2] ++;

      c1 = c2;

    }

  // Generate upper position

  for (i=1;i<65536;i++)

    ftab[i] += ftab[i-1];

  // Fill rank array with upper bound

  c1 = data[0];

  for (i=0; i

    {

      unsigned char c2 = data[i+1];

      rank[i] = ftab[(c1<<8)|c2];

      c1 = c2;

    }

  // Fill posn array (backwards)

  c1 = data[size-2];

  for (i=size-3; i>=0; i--)

    {

      unsigned char c2 = data[i];

      posn[ ftab[(c2<<8)|c1]-- ] = i;

      c1 = c2;

    }

  // Fixup marker stuff

  ASSERT(data[size-1]==0);

  c1 = data[size-2];

  posn[0] = size-1;

  posn[ ftab[(c1<<8)] ] = size-2;

  rank[size-1] = 0;

  rank[size-2] = ftab[(c1<<8)];

  // Extra element

  rank[size] = -1;

}

// _BSort::run -- main sort loop

void

_BSort::run(int &markerpos)

{

  int lo, hi;

  ASSERT(size>0);

  ASSERT(data[size-1]==0);

#ifdef BSORT_TIMER

  long start = GOS::ticks();

#endif  

  // Step 1: Radix sort 

  int depth = 0;

  if (size > RADIX_THRESH)

    { 

      radixsort16();

      depth=2;

    }

  else

    { 

      radixsort8(); 

      depth=1;

    }

  // Step 2: Perform presort to depth PRESORT_DEPTH

  for (lo=0; lo

    {

      hi = rank[posn[lo]];

      if (lo < hi)

        quicksort3d(lo, hi, depth);

      lo = hi;

    }

  depth = PRESORT_DEPTH;

#ifdef BSORT_TIMER

  long middle = GOS::ticks();

#endif  

  // Step 3: Perform rank doubling

  int again = 1;

  while (again)

    {

      again = 0;

      int sorted_lo = 0;

      for (lo=0; lo

        {

          hi = rank[posn[lo]&0xffffff];

          if (lo == hi)

            {

              lo += (posn[lo]>>24) & 0xff;

            }

          else

            {

              if (hi-lo < RANKSORT_THRESH)

                {

                  ranksort(lo, hi, depth);

                }

              else

                {

                  again += 1;

                  while (sorted_lo < lo-1)

                    {

                      int step = mini(255, lo-1-sorted_lo);

                      posn[sorted_lo] = (posn[sorted_lo]&0xffffff) | (step<<24);

                      sorted_lo += step+1;

                    }

                  quicksort3r(lo, hi, depth);

                  sorted_lo = hi + 1;

                }

              lo = hi;

            }

        }

      // Finish threading

      while (sorted_lo < lo-1)

        {

          int step = mini(255, lo-1-sorted_lo);

          posn[sorted_lo] = (posn[sorted_lo]&0xffffff) | (step<<24);

          sorted_lo += step+1;

        }

      // Double depth

      depth += depth;

    }

  // Step 4: Permute data

  int i;

  markerpos = -1;

  for (i=0; i

    rank[i] = data[i];

  for (i=0; i

    {

      int j = posn[i] & 0xffffff;

      if (j>0) 

        { 

          data[i] = rank[j-1];

        } 

      else 

        {

          data[i] = 0;

          markerpos = i;

        }

    }

  ASSERT(markerpos>=0 && markerpos

#ifdef BSORT_TIMER

  long end = GOS::ticks();

  DjVuPrintErrorUTF8("Sorting time: %d bytes in %ld + %ld = %ld ms\n", 

          size-1, middle-start, end-middle, end-start);

#endif  

}

// ========================================

// -- Encoding

static void

encode_raw(ZPCodec &zp, int bits, int x)

{

  int n = 1;

  int m = (1<

  while (n < m)

    {

      x = (x & (m-1)) << 1;

      int b = (x >> bits);

      zp.encoder(b);

      n = (n<<1) | b;

    }

}

static inline void

encode_binary(ZPCodec &zp, BitContext *ctx, int bits, int x)

{

  // Require 2^bits-1  contexts

  int n = 1;

  int m = (1<

  ctx = ctx - 1;

  while (n < m)

    {

      x = (x & (m-1)) << 1;

      int b = (x >> bits);

      zp.encoder(b, ctx[n]);

      n = (n<<1) | b;

    }

}

class BSByteStream::Encode : public BSByteStream

{

public:

  /** Creates a Static object for allocating the memory area of

      length #sz# starting at address #buffer#. */

  Encode(GP<ByteStream> bs);

  ~Encode();

  void init(const int encoding);

  // Virtual functions

  virtual size_t write(const void *buffer, size_t sz);

  virtual void flush(void);

protected:

  unsigned int encode(void);

};

unsigned int

BSByteStream::Encode::encode()

{ 

  /////////////////////////////////

  ////////////  Block Sort Tranform

  int markerpos = size-1;

  blocksort(data,size,markerpos);

  /////////////////////////////////

  //////////// Encode Output Stream

  // Header

  ZPCodec &zp=*gzp;

  encode_raw(zp, 24, size);

  // Determine and Encode Estimation Speed

  int fshift = 0;

  if (size < FREQS0)

    { fshift=0; zp.encoder(0); }

  else if (size < FREQS1)

    { fshift = 1; zp.encoder(1); zp.encoder(0); }

  else

    { fshift = 2; zp.encoder(1); zp.encoder(1); }

  // MTF

  unsigned char mtf[256];

  unsigned char rmtf[256];

  unsigned int  freq[FREQMAX];

  int m = 0;

  for (m=0; m<256; m++)

    mtf[m] = m;

  for (m=0; m<256; m++)

    rmtf[mtf[m]] = m;

  int fadd = 4;

  for (m=0; m

    freq[m] = 0;

  // Encode

  int i;

  int mtfno = 3;

  for (i=0; i

    {

      // Get MTF data

      int c = data[i];

      int ctxid = CTXIDS-1;

      if (ctxid>mtfno) ctxid=mtfno;

      mtfno = rmtf[c];

      if (i==markerpos)

        mtfno = 256;

      // Encode using ZPCoder

      int b;

      BitContext *cx = ctx;

      b = (mtfno==0);

      zp.encoder(b, cx[ctxid]);

      if (b) goto rotate; cx+=CTXIDS;

      b = (mtfno==1);

      zp.encoder(b, cx[ctxid]);

      if (b) goto rotate; cx+=CTXIDS;

      b = (mtfno<4);

      zp.encoder(b, cx[0]);

      if (b) { encode_binary(zp,cx+1,1,mtfno-2); goto rotate; } 

      cx+=1+1;

      b = (mtfno<8);

      zp.encoder(b, cx[0]);

      if (b) { encode_binary(zp,cx+1,2,mtfno-4); goto rotate; } 

      cx+=1+3;

      b = (mtfno<16);

      zp.encoder(b, cx[0]);

      if (b) { encode_binary(zp,cx+1,3,mtfno-8); goto rotate; } 

      cx+=1+7;

      b = (mtfno<32);

      zp.encoder(b, cx[0]);

      if (b) { encode_binary(zp,cx+1,4,mtfno-16); goto rotate; } 

      cx+=1+15;

      b = (mtfno<64);

      zp.encoder(b, cx[0]);

      if (b) { encode_binary(zp,cx+1,5,mtfno-32); goto rotate; } 

      cx+=1+31;

      b = (mtfno<128);

      zp.encoder(b, cx[0]);

      if (b) { encode_binary(zp,cx+1,6,mtfno-64); goto rotate; } 

      cx+=1+63;

      b = (mtfno<256);

      zp.encoder(b, cx[0]);

      if (b) { encode_binary(zp,cx+1,7,mtfno-128); goto rotate; } 

      continue;

      // Rotate MTF according to empirical frequencies (new!)

    rotate: