/*
  座標定義用構造体
*/
template< class T > struct Coord
{
  T x; // x 座標
  T y; // y 座標

  /* コンストラクタ */

  // デフォルト・コンストラクタ
  // ( x, y ) = ( 0, 0 ) で初期化される
  Coord() : x( 0 ), y ( 0 ) {}

  // x, y 座標を指定して構築
  Coord( T x_, T y_ ) : x( x_ ), y ( y_ ) {}

  // 異なる型の座標 c から構築
  template< class U >
  Coord( const Coord< U >& c ) : x( c.x ), y( c.y ) {}
};

/*
  ビットプレーン構造体
*/
struct BitPlane
{
  unsigned int coeff;     // 係数(絶対値)
  bool isPos;             // 係数は正か
  unsigned char signFlag; // 有意性
  unsigned char pass;     // 現在のパス

  // コンストラクタ
  BitPlane()
  : coeff( 0 ), isPos( true ), signFlag( 0 ), pass( EBCOT_CU_PASS ) {}
};

/*
  コードブロック
*/
class CodeBlock
{
  std::vector< BitPlane > bitPlane_; // ビットプレーン
  Coord< size_t > size_;             // ビットプレーンのサイズ
  size_t spriteCount_;               // ビットプレーンの高さ(スプライト数)

 public:

  // デフォルト・コンストラクタ
  CodeBlock()
    : bitPlane_(), size_( 0, 0 ), spriteCount_( 0 ) {}

  // ビットプレーンの幅を返す
  size_t width() const
  { return( size_.x ); }

  // ビットプレーンの高さを返す
  size_t height() const
  { return( size_.y ); }

  // ビットプレーンの縦方向のスプライト数を返す
  size_t spriteCount() const
  { return( spriteCount_ ); }
};

/*****************************************************************************************
  定数宣言
*****************************************************************************************/
const unsigned int EBCOT_SPRITE_SIZE = 4; // sprite の縦方向のサイズ

/* コンテキスト・ラベル */
enum JPEG2000_CONTEXT_LABEL
{
  CL_SP_CODING_0 = 0,
  CL_SP_CODING_1 = 1,
  CL_SP_CODING_2 = 2,
  CL_SP_CODING_3 = 3,
  CL_SP_CODING_4 = 4,
  CL_SP_CODING_5 = 5,
  CL_SP_CODING_6 = 6,
  CL_SP_CODING_7 = 7,
  CL_SP_CODING_8 = 8,
  CL_SIGN_CODING_00 = 9,
  CL_SIGN_CODING_01 = 10,
  CL_SIGN_CODING_PM = 11,
  CL_SIGN_CODING_10 = 12,
  CL_SIGN_CODING_11 = 13,
  CL_MR_CODING_NEIGH0 = 14,
  CL_MR_CODING_NEIGH1 = 15,
  CL_MR_CODING_MULTI = 16,
  CL_RUNLENGTH_CODING = 17,
  CL_UNIFORM = 18,
  CL_SIZE = 19,
};

/*
  サブバンドに付加する定数値
  コンテキストラベル 0-8 を決めるための定義に利用する
*/
enum EBCOT_SUBBAND
{
  EBCOT_SUBBAND_LL = 0,   // スケーリング係数
  EBCOT_SUBBAND_LH = 0,   // 垂直方向のウェーブレット係数
  EBCOT_SUBBAND_HL = 1,   // 水平方向のウェーブレット係数
  EBCOT_SUBBAND_HH = 2,   // 対角方向のウェーブレット係数
  EBCOT_SUBBAND_SIZE = 3, // 定数値の数
};

/* 符号化パスに対する定数値 */
enum EBCOT_PASS
{
  EBCOT_CU_PASS = 0, // Cleanup Pass
  EBCOT_SP_PASS = 1, // Significance Propagation Pass
  EBCOT_MR_PASS = 2, // Magnitude Refinement Pass
};

/*****************************************************************************************
  関数の型定義
*****************************************************************************************/
typedef ContextLabel (*significance_encode_type)( CodeBlock*, Coord< size_t >, unsigned int, unsigned int, Encoder&, bool );
typedef ContextLabel (*significance_decode_type)( CodeBlock*, Coord< size_t >, unsigned int, unsigned int, Decoder&, bool );
typedef ContextLabel (*sign_encode_type)( CodeBlock*, Coord< size_t >, Encoder& );
typedef ContextLabel (*sign_decode_type)( CodeBlock*, Coord< size_t >, Decoder& );

/*****************************************************************************************
  Significant Coding Context Labelの定義
*****************************************************************************************/
const size_t EBCOT_SIGN_CL_SIZE = 9; // Significance Propagetion のコンテキストラベル数

struct SignificantContextLabelType
{
  unsigned char h_min; // 有意な水平成分の数最小値 min(ΣHi)
  unsigned char h_max; // 有意な水平成分の数最大値 max(ΣHi)
  unsigned char v_min; // 有意な垂直成分の数最小値 min(ΣVi)
  unsigned char v_max; // 有意な垂直成分の数最大値 max(ΣVi)
  unsigned char d_min; // 有意な対角成分の数最小値 min(ΣDi)
  unsigned char d_max; // 有意な対角成分の数最大値 max(ΣDi)
};

SignificantContextLabelType SignCL[EBCOT_SUBBAND_SIZE][EBCOT_SIGN_CL_SIZE] = {
  {
    // min(ΣHi),max(ΣHi),min(ΣVi),max(ΣVi),min(ΣDi),max(ΣDi)
    { 0, 0, 0, 0, 0, 0, }, // LL,LH subband
    { 0, 0, 0, 0, 1, 1, },
    { 0, 0, 0, 0, 2, 4, },
    { 0, 0, 1, 1, 0, 4, },
    { 0, 0, 2, 2, 0, 4, },
    { 1, 1, 0, 0, 0, 0, },
    { 1, 1, 0, 0, 1, 4, },
    { 1, 1, 1, 2, 0, 4, },
    { 2, 2, 0, 2, 0, 4, },
  },
  {
    // min(ΣHi),max(ΣHi),min(ΣVi),max(ΣVi),min(ΣDi),max(ΣDi)
    { 0, 0, 0, 0, 0, 0, }, // HL subband
    { 0, 0, 0, 0, 1, 1, },
    { 0, 0, 0, 0, 2, 4, },
    { 1, 1, 0, 0, 0, 4, },
    { 2, 2, 0, 0, 0, 4, },
    { 0, 0, 1, 1, 0, 0, },
    { 0, 0, 1, 1, 1, 4, },
    { 1, 2, 1, 1, 0, 4, },
    { 0, 2, 2, 2, 0, 4, },
  },
  {
    // min(ΣHi),max(ΣHi),min(ΣVi),max(ΣVi),min(ΣDi),max(ΣDi)
    { 0, 0, 0, 0, 0, 0, }, // HH subband
    { 1, 1, 1, 1, 0, 0, },
    { 2, 4, 2, 4, 0, 0, },
    { 0, 0, 0, 0, 1, 1, },
    { 1, 1, 1, 1, 1, 1, },
    { 2, 4, 2, 4, 1, 1, },
    { 0, 0, 0, 0, 2, 2, },
    { 1, 4, 1, 4, 2, 2, },
    { 0, 4, 0, 4, 3, 4, },
  },
};

/*****************************************************************************************
  CodeBlock のメンバ関数
*****************************************************************************************/
/*
  座標 c の係数・または近傍の係数のビットプレーンへの参照を返す

  近傍状態を確認する時に範囲外を参照する可能性があるため、実際のサイズより上下左右に 1 ピクセル分の余白がある。
  そのため、左上の原点は ( 0, 0 ) ではなく ( 1, 1 ) となっていることに注意。
*/
BitPlane& CodeBlock::operator[]( Coord< size_t > c ) { return( bitPlane_.at( pos( c.x + 1, c.y + 1 ) ) ); } // 現在位置
BitPlane& CodeBlock::operator()( size_t x, size_t y ) { return( bitPlane_.at( pos( x + 1, y + 1 ) ) ); }    // 現在位置
const BitPlane& CodeBlock::operator[]( Coord< size_t > c ) const { return( bitPlane_.at( pos( c.x + 1, c.y + 1 ) ) ); } // 現在位置
const BitPlane& CodeBlock::operator()( size_t x, size_t y ) const { return( bitPlane_.at( pos( x + 1, y + 1 ) ) ); }    // 現在位置

const BitPlane& CodeBlock::d0( Coord< size_t > c ) const { return( bitPlane_.at( pos( c.x, c.y ) ) ); }         // 左上
const BitPlane& CodeBlock::d1( Coord< size_t > c ) const { return( bitPlane_.at( pos( c.x + 2, c.y ) ) ); }     // 右上
const BitPlane& CodeBlock::d2( Coord< size_t > c ) const { return( bitPlane_.at( pos( c.x, c.y + 2 ) ) ); }     // 左下
const BitPlane& CodeBlock::d3( Coord< size_t > c ) const { return( bitPlane_.at( pos( c.x + 2, c.y + 2 ) ) ); } // 右下
const BitPlane& CodeBlock::h0( Coord< size_t > c ) const { return( bitPlane_.at( pos( c.x, c.y + 1 ) ) ); }     // 左
const BitPlane& CodeBlock::h1( Coord< size_t > c ) const { return( bitPlane_.at( pos( c.x + 2, c.y + 1 ) ) ); } // 右
const BitPlane& CodeBlock::v0( Coord< size_t > c ) const { return( bitPlane_.at( pos( c.x + 1, c.y ) ) ); }     // 上
const BitPlane& CodeBlock::v1( Coord< size_t > c ) const { return( bitPlane_.at( pos( c.x + 1, c.y + 2 ) ) ); } // 下

/*****************************************************************************************
  EBCOT 処理用関数
*****************************************************************************************/
// 係数 coeff の下位から bit 番目のビット状態を返す
inline bool GetBit( unsigned int coeff, unsigned int bit )
{ return( ( ( coeff >> bit ) & 1 ) != 0 ); }

// 係数 coeff の下位から bit 番目のビットを立てる
inline void SetBit( unsigned int* coeff, unsigned int bit )
{ *coeff |= ( 1 << bit ); }

/*
  現係数 codeBlock の位置 c の近傍状態を h(水平成分), v(垂直成分), d(対角成分) に返す

  codeBlock : 現係数
  c : 現係数の位置
*/
void GetNeighborState( const CodeBlock& codeBlock, Coord< size_t > c, unsigned char* h, unsigned char* v, unsigned char* d )
{
  *h = *v = *d = 0;
  if ( ( codeBlock.h0( c ) ).signFlag > 0 ) ++( *h );
  if ( ( codeBlock.h1( c ) ).signFlag > 0 ) ++( *h );
  if ( ( codeBlock.v0( c ) ).signFlag > 0 ) ++( *v );
  if ( ( codeBlock.v1( c ) ).signFlag > 0 ) ++( *v );
  if ( ( codeBlock.d0( c ) ).signFlag > 0 ) ++( *d );
  if ( ( codeBlock.d1( c ) ).signFlag > 0 ) ++( *d );
  if ( ( codeBlock.d2( c ) ).signFlag > 0 ) ++( *d );
  if ( ( codeBlock.d3( c ) ).signFlag > 0 ) ++( *d );
}

/*
  Significance Propagetion Pass と Cleanup Pass に対するコンテキストラベルを返す

  codeBlock : 現係数
  c : 現係数の位置
  subband : サブバンド

  戻り値 : コンテクストラベル
*/
ContextLabel GetSignificance_CL( const CodeBlock& codeBlock, Coord< size_t > c, unsigned int subband )
{
  unsigned char h, v, d; // 水平・垂直・対角成分の有意ビット数
  ContextLabel cl;       // コンテキストラベル

  GetNeighborState( codeBlock, c, &h, &v, &d );

  // HH subbandの場合は h + v で比較
  if ( subband == EBCOT_SUBBAND_HH ) {
    h += v;
    v = h;
  }

  // サブバンド別の、近傍係数に対するコンテキストラベル表からコンテキストラベルを決定
  SignificantContextLabelType* signCL = SignCL[subband];
  for ( cl = EBCOT_SIGN_CL_SIZE - 1 ; cl > 0 ; --cl ) {
    if ( ( signCL[cl] ).h_min <= h && ( signCL[cl] ).h_max >= h &&
         ( signCL[cl] ).v_min <= v && ( signCL[cl] ).v_max >= v &&
         ( signCL[cl] ).d_min <= d && ( signCL[cl] ).d_max >= d )
      break;
  }

  return( cl );
}

/*
  Significance Coding

  近傍状態からコンテクストラベルを決定し、符号化/復号化を行う。

  codeBlock : コードブロックへのポインタ
  c : 現係数の位置
  subband : サブバンド(LL/LH/HL/HH)
  bit : BitPlaneのビット位置
  encoder/decoder : 符号化/復号化処理用関数オブジェクト
  isCleanUp : Clean Up パスから呼び出されたものか

  戻り値 : コンテクストラベル
*/
ContextLabel SignificanceEncode( CodeBlock* codeBlock, Coord< size_t > c, unsigned int subband, unsigned int bit, Encoder& encoder, bool isCleanUp )
{
  BitPlane& current_bp = (*codeBlock)[c]; // 現係数

  if ( current_bp.signFlag > 0 ) return( 0 ); // 現係数がすでに有意ならスキップ(ゼロを返す)

  ContextLabel cl = GetSignificance_CL( *codeBlock, c, subband ); // コンテキストラベル
  if ( ( cl == 0 ) && ( ! isCleanUp ) ) return( cl );  // CleanUp の場合、符号化は cl = 0 でも行う

  bool b = GetBit( (*codeBlock)[c].coeff, bit );
  if ( b )
    current_bp.signFlag = 1;
  encoder( b, cl );

  return( cl );
}
ContextLabel SignificanceDecode( CodeBlock* codeBlock, Coord< size_t > c, unsigned int subband, unsigned int bit, Decoder& decoder, bool isCleanUp )
{
  BitPlane& current_bp = (*codeBlock)[c]; // 現係数

  if ( current_bp.signFlag > 0 ) return( 0 ); // 現係数がすでに有意ならスキップ(ゼロを返す)

  ContextLabel cl = GetSignificance_CL( *codeBlock, c, subband ); // コンテキストラベル
  if ( ( cl == 0 ) && ( ! isCleanUp ) ) return( cl );  // CleanUp の場合、符号化は cl = 0 でも行う

  if ( decoder( cl ) ) {
    current_bp.signFlag = 1;
    SetBit( &( (*codeBlock)[c].coeff ), bit );
  }

  return( cl );
}

/*
  極性ビットの符号化のための指標を決定する

  hv0 : 垂直/水平近傍 1
  hv1 : 垂直/水平近傍 2

  戻り値 : 指標
*/
int GetPolarIndex( const BitPlane& hv0, const BitPlane& hv1 )
{
  // どちらも有意
  if ( hv0.signFlag > 0 && hv1.signFlag > 0 ) {
    if ( hv0.isPos && hv1.isPos ) return( 1 );
    else if ( ( ! hv0.isPos ) && ( ! hv1.isPos ) ) return( -1 );
    else return( 0 );
  // hv0 が有意
  } else if ( hv0.signFlag > 0 ) {
    return( ( hv0.isPos ) ? 1 : -1 );
  // hv1 が有意
  } else if ( hv1.signFlag > 0 ) {
    return( ( hv1.isPos ) ? 1 : -1 );
  // 両方とも有意でない
  } else {
    return( 0 );
  }
}

/*
  極性ビットの排他的論理和(XOR)を返す

  sign : 極性ビット
  h_c : 水平指標(Horizontal Contribution)

  戻り値 : 正/負(=false/true) と XORbit との排他的論理和
*/
bool GetXorbitOfSign( bool sign, int h_c )
{
  // 水平指標が 0 以上の場合 XORbit は false、そうでなければ true を取る
  return( ( h_c >= 0 ) ? sign ^ false : sign ^ true );
}

/*
  極性符号化に対するコンテキストラベルを返す

  codeBlock : コードブロックへの参照
  c : 現係数の位置
  sign : 係数の極性へのポインタ( NULL なら無視 )
*/
ContextLabel GetSign_CL( const CodeBlock& codeBlock, Coord< size_t > c, bool* sign )
{
  const BitPlane& current_bp = codeBlock[c]; // 現係数
  ContextLabel cl = 0; // コンテキストラベル

  int h_c = GetPolarIndex( codeBlock.h0( c ), codeBlock.h1( c ) ); // 水平指標(Horizontal Contribution)
  int v_c = GetPolarIndex( codeBlock.v0( c ), codeBlock.v1( c ) ); // 垂直指標(Vertical Contribution)

  // 現係数の極性ビットの排他的論理和(XOR)を取得する
  if ( sign != 0 )
    *sign = GetXorbitOfSign( ! current_bp.isPos, h_c );

  switch( h_c ) {
  case 1:
    cl = ( v_c > 0 ) ? CL_SIGN_CODING_11 : ( ( v_c < 0 ) ? CL_SIGN_CODING_PM : CL_SIGN_CODING_10 );
    break;
  case 0:
    cl = ( v_c != 0 ) ? CL_SIGN_CODING_01 : CL_SIGN_CODING_00;
    break;
  case -1:
    cl = ( v_c > 0 ) ? CL_SIGN_CODING_PM : ( ( v_c < 0 ) ? CL_SIGN_CODING_11 : CL_SIGN_CODING_10 );
    break;
  }

  return( cl );
}

/*
  Sign Coding

  極性ビットの符号化/復号化

  codeBlock : コードブロックへのポインタ
  c : 現係数の位置
  encoder/decoder : 符号化/復号化処理用関数オブジェクト

  戻り値 : コンテクストラベル
*/
ContextLabel SignEncode( CodeBlock* codeBlock, Coord< size_t > c, Encoder& encoder )
{
  bool sign; // 係数の極性

  ContextLabel cl = GetSign_CL( *codeBlock, c, &sign ); // コンテキストラベル
  encoder( sign, cl );

  return( cl );
}

ContextLabel SignDecode( CodeBlock* codeBlock, Coord< size_t > c, Decoder& decoder )
{
  ContextLabel cl = GetSign_CL( *codeBlock, c, 0 ); // コンテキストラベル

  bool d = decoder( cl ); // Decision

  // 正/負(=0/1) と XORbit との排他的論理和
  if ( GetXorbitOfSign( d, GetPolarIndex( codeBlock->h0( c ), codeBlock->h1( c ) ) ) ) {
    (*codeBlock)[c].isPos = false;
  }
  return( cl );
}

/*
  Significance Propagation Pass

  codeBlock : コードブロックへのポインタ
  subband : サブバンド
  bit : BitPlane のビット位置
  significanceOp : Significance Coding function
  signOp : Sign Coding function
  coderOp : 符号化/復号化処理用関数オブジェクト
*/
template< class SignificanceOp, class SignOp, class CoderOp >
void SigProPass( CodeBlock* codeBlock, unsigned int subband, unsigned int bit,
                 SignificanceOp significanceOp, SignOp signOp, CoderOp& coderOp )
{
  for ( size_t sy = 0 ; sy < codeBlock->spriteCount() ; ++sy ) {
    for ( Coord< size_t > c( 0, 0 ) ; c.x < codeBlock->width() ; ++( c.x ) ) {
      for ( c.y = sy * EBCOT_SPRITE_SIZE ; c.y < ( sy + 1 ) * EBCOT_SPRITE_SIZE ; ++( c.y ) ) {
        if ( significanceOp( codeBlock, c, subband, bit, coderOp, false ) > 0 ) {
          (*codeBlock)[c].pass = EBCOT_SP_PASS;
          if ( (*codeBlock)[c].signFlag > 0 )
            signOp( codeBlock, c, coderOp );
        }
      }
    }
  }
}

/*****************************************************************************************
  関数の型定義
*****************************************************************************************/
typedef ContextLabel (*mag_ref_encode_type)( CodeBlock*, Coord< size_t >, unsigned int, Encoder& );
typedef ContextLabel (*mag_ref_decode_type)( CodeBlock*, Coord< size_t >, unsigned int, Decoder& );

/*
  Magnitude Refinement Passに対するコンテキストラベルを返す

  codeBlock : コードブロックへのポインタ
  c : 現係数の位置

  戻り値 : コンテキストラベル
*/
ContextLabel GetMR_CL( CodeBlock* codeBlock, Coord< size_t > c )
{
  BitPlane& current_bp = (*codeBlock)[c]; // 現係数

  ContextLabel cl = 0;   // コンテキストラベル

  switch( current_bp.signFlag ) {
  case 0: // まだ有意でなければスキップ ( ゼロを返す )
    break;
  case 1: // 直前の Significance Propagation Passで有意に変化 ( 何もせずゼロを返す )
    ++( current_bp.signFlag ); // signFlag を次にセット
    break;
  case 2: // 最初の Maginitude Refinement Pass
    ++( current_bp.signFlag ); // signFlag を次にセット
    unsigned char h, v, d;     // 水平・垂直・対角成分の有意ビット数
    GetNeighborState( *codeBlock, c, &h, &v, &d );
    cl = ( h + v + d >= 1 ) ? CL_MR_CODING_NEIGH1 : CL_MR_CODING_NEIGH0;
    break;
  case 3: // 二回目以降の Maginitude Refinement Pass
    cl = CL_MR_CODING_MULTI;
    break;
  }

  return( cl );
}

/*
  Maginitude Refinement Coding

  すでに有意判定された係数ビットの符号化/復号化

  codeBlock : コードブロックへのポインタ
  c : 現係数の位置
  bit : BitPlaneのビット位置
  encoder/decoder : 符号化/復号化処理用関数オブジェクト

  戻り値 : コンテクストラベル
*/
ContextLabel MR_Encode( CodeBlock* codeBlock, Coord< size_t > c, unsigned int bit, Encoder& encoder )
{
  ContextLabel cl = GetMR_CL( codeBlock, c );
  if ( cl > 0 )
    encoder( GetBit( (*codeBlock)[c].coeff, bit ), cl );

  return( cl );
}

ContextLabel MR_Decode( CodeBlock* codeBlock, Coord< size_t > c, unsigned int bit, Decoder& decoder )
{
  ContextLabel cl = GetMR_CL( codeBlock, c );
  if ( cl > 0 ) {
    if ( decoder( cl ) ) SetBit( &( (*codeBlock)[c].coeff ), bit );
  }

  return( cl );
}

/*
  Magnitude Refinement Pass

  codeBlock : コードブロックへのポインタ
  bit : BitPlane のビット位置
  magRefOp : Magnitude Refinement Coding function
  coderOp : 符号化/復号化処理用関数オブジェクト
*/
template< class MagRefOp, class CoderOp >
void MagRefPass( CodeBlock* codeBlock, unsigned int bit,
                 MagRefOp magRefOp, CoderOp& coderOp )
{
  for ( size_t sy = 0 ; sy < codeBlock->spriteCount() ; ++sy ) {
    for ( Coord< size_t > c( 0, 0 ) ; c.x < codeBlock->width() ; ++( c.x ) ) {
      for ( c.y = sy * EBCOT_SPRITE_SIZE ; c.y < ( sy + 1 ) * EBCOT_SPRITE_SIZE ; ++( c.y ) ) {
        if ( magRefOp( codeBlock, c, bit, coderOp ) > 0 )
          (*codeBlock)[c].pass = EBCOT_MR_PASS;
      }
    }
  }
}

/*****************************************************************************************
  関数の型定義
*****************************************************************************************/
typedef unsigned char (*runlength_encode_type)( CodeBlock*, Coord< size_t >, unsigned int, unsigned int, Encoder& );
typedef unsigned char (*runlength_decode_type)( CodeBlock*, Coord< size_t >, unsigned int, unsigned int, Decoder& );

/*
  現係数 codeBlock の位置 c の近傍状態が全て有意でなければ true を返す
*/
bool NotSignNeighborState( const CodeBlock& codeBlock, Coord< size_t > c )
{
  if ( ( codeBlock.h0( c ) ).signFlag > 0 ) return( false );
  if ( ( codeBlock.h1( c ) ).signFlag > 0 ) return( false );
  if ( ( codeBlock.v0( c ) ).signFlag > 0 ) return( false );
  if ( ( codeBlock.v1( c ) ).signFlag > 0 ) return( false );
  if ( ( codeBlock.d0( c ) ).signFlag > 0 ) return( false );
  if ( ( codeBlock.d1( c ) ).signFlag > 0 ) return( false );
  if ( ( codeBlock.d2( c ) ).signFlag > 0 ) return( false );
  if ( ( codeBlock.d3( c ) ).signFlag > 0 ) return( false );

  return( true );
}

/*
  Runlength Codingが必要かを判別する

  現 SPRITE 内に一つでも Cleanup Pass でない係数があったら不要と判断

  codeBlock : コードブロックへの参照
  c : 現SPRITEの位置

  戻り値 : 必要なら true を返す
*/
bool NeedRunlengthCoding( const CodeBlock& codeBlock, Coord< size_t > c )
{
  for ( unsigned int i = 0 ; i < EBCOT_SPRITE_SIZE ; i++ ) {
    if ( codeBlock( c.x, c.y + i ).pass != EBCOT_CU_PASS )
      return( false );
    if ( ! NotSignNeighborState( codeBlock, c ) )
      return( false );
  }

  return( true );
}

/*
  Run Length Coding

  ランレングス符号化/復号化

  codeBlock : コードブロックへのポインタ
  c : 現係数の X 座標と現係数のある SPRITE の先頭 Y 座標
  subband : サブバンド
  bit : ビット位置
  encoder/decoder : 符号化/復号化処理用関数オブジェクト

  戻り値 : ランレングスコンテクストのシンボル( 4 つのビットが全てゼロなら 0 )
*/
void RunlengthEncode( CodeBlock* codeBlock, Coord< size_t > c, unsigned int subband, unsigned int bit, Encoder& encoder )
{
  // SPRITE内に有意係数を持った係数があるか
  bool runLenSymbol = false;
  // SPRITEにおいて最初に有意係数が見つかった位置を示すシンボル 上から順に 00, 01, 10, 11
  unsigned char uniformSymbol = 0;

  // SPRITE内の有意係数を探す
  for ( ; uniformSymbol < EBCOT_SPRITE_SIZE ; ++uniformSymbol ) {
    if ( GetBit( (*codeBlock)( c.x, c.y + uniformSymbol ).coeff, bit ) ) {
      // 有意係数が次のビットプレーンで Maginitude Refinement Coding を実行できるように signFlag を 2 にする
      ( (*codeBlock)( c.x, c.y + uniformSymbol ) ).signFlag = 2;
      runLenSymbol = true;
      break;
    }
  }

  // runLenSymbolの符号化
  encoder( runLenSymbol, CL_RUNLENGTH_CODING );
  if ( ! runLenSymbol ) return;

  // uniformSymbolの符号化
  encoder( ( ( uniformSymbol >> 1 ) & 1 ) != 0, CL_UNIFORM );
  encoder( ( uniformSymbol & 1 ) != 0, CL_UNIFORM );
  SignEncode( codeBlock, Coord< size_t >( c.x, c.y + uniformSymbol ), encoder );

  // 残りの係数をSignificance Coding
  while ( ++uniformSymbol < EBCOT_SPRITE_SIZE ) {
    SignificanceEncode( codeBlock, Coord< size_t >( c.x, c.y + uniformSymbol ), subband, bit, encoder, true );
    if ( (*codeBlock)( c.x, c.y + uniformSymbol ).signFlag > 0 ) {
      // 有意の場合、次のビットプレーンで Maginitude Refinement Coding が実行できるように signFlag を 2 にする
      ( (*codeBlock)( c.x, c.y + uniformSymbol ) ).signFlag = 2;
      SignEncode( codeBlock, Coord< size_t >( c.x, c.y + uniformSymbol ), encoder );
    }
  }
}

void RunlengthDecode( CodeBlock* codeBlock, Coord< size_t > c, unsigned int subband, unsigned int bit, Decoder& decoder )
{
  // SPRITE内に有意係数を持った係数があるか
  if ( ! decoder( CL_RUNLENGTH_CODING ) ) return;

  // SPRITEにおいて最初に有意係数が見つかった位置を示すシンボル 上から順に 00, 01, 10, 11
  unsigned char uniformSymbol = ( decoder( CL_UNIFORM ) ) ? 2 : 0;
  if ( decoder( CL_UNIFORM ) ) ++uniformSymbol;

  SetBit( &( (*codeBlock)( c.x, c.y + uniformSymbol ).coeff ), bit );
  SignDecode( codeBlock, Coord< size_t >( c.x, c.y + uniformSymbol ), decoder );

  // 有意係数が次のビットプレーンで Maginitude Refinement Coding を実行できるように signFlag を 2 にする
  (*codeBlock)( c.x, c.y + uniformSymbol ).signFlag = 2;

  // 残りの係数をSignificance Coding
  while ( ++uniformSymbol < EBCOT_SPRITE_SIZE ) {
    SignificanceDecode( codeBlock, Coord< size_t >( c.x, c.y + uniformSymbol ), subband, bit, decoder, true );
    if ( (*codeBlock)( c.x, c.y + uniformSymbol ).signFlag > 0 ) {
      // 有意の場合、次のビットプレーンで Maginitude Refinement Coding が実行できるように signFlag を 2 にする
      (*codeBlock)( c.x, c.y + uniformSymbol ).signFlag = 2;
      SignDecode( codeBlock, Coord< size_t >( c.x, c.y + uniformSymbol ), decoder );
    }
  }
}

/*
  Cleanup Pass

  codeBlock : コードブロックへのポインタ
  subband : サブバンド
  bit : BitPlane のビット位置
  runlengthOp : Runlength Coding function
  significanceOp : Significance Coding function
  signOp : Sign Coding function
  coderOp : 符号化/復号化処理用関数オブジェクト
*/
template< class RunlengthOp, class SignificanceOp, class SignOp, class CoderOp >
void CleanupPass( CodeBlock* codeBlock, unsigned int subband, unsigned int bit,
                  RunlengthOp runlengthOp, SignificanceOp significanceOp, SignOp signOp, CoderOp& coderOp )
{
  for ( size_t sy = 0 ; sy < codeBlock->spriteCount() ; ++sy ) {
    for ( Coord< size_t > c( 0, sy * EBCOT_SPRITE_SIZE ) ; c.x < codeBlock->width() ; c.y = sy * EBCOT_SPRITE_SIZE, ++( c.x ) ) {
      if ( NeedRunlengthCoding( *codeBlock, c ) ) {
        runlengthOp( codeBlock, c, subband, bit, coderOp );
      } else {
        for ( ; c.y < ( sy + 1 ) * EBCOT_SPRITE_SIZE ; ++( c.y ) ) {
          BitPlane& current_bp = (*codeBlock)[c]; // 現係数
          if ( current_bp.pass != EBCOT_CU_PASS ) continue;
          significanceOp( codeBlock, c, subband, bit, coderOp, true );
          if ( current_bp.signFlag > 0 ) {
            // 有意の場合、次のビットプレーンで Maginitude Refinement Coding が実行できるように signFlag を 2 にする
            (*codeBlock)[c].signFlag = 2;
            signOp( codeBlock, c, coderOp );
            current_bp.pass = EBCOT_MR_PASS;
          }
        }
      }
    }
  }
}

const unsigned int EBCOT_BITSIZE_BIT = CHAR_BIT;                           // 最上位ビット位置の符号化ビット数
const unsigned int EBCOT_BITSIZE_MAX = ( 1 << EBCOT_BITSIZE_BIT ) - 1;     // 最上位ビット位置の最大値
const unsigned int EBCOT_BLOCKSIZE_BIT = 12;                               // コードブロックサイズの符号化ビット数
const unsigned int EBCOT_BLOCKSIZE_MAX = ( 1 << EBCOT_BLOCKSIZE_BIT ) - 1; // コードブロックサイズの最大値

/*
  有意な係数を持つビット位置を返す

  codeBlock : コードブロックへの参照

  戻り値 : 有意係数を持った最上位のビット位置
           (ビット位置は最下位を1とする)
           0 の場合は全てが 0 であることを意味する。
*/
unsigned int GetSignificantBitPlane( const CodeBlock& codeBlock )
{
  for ( unsigned int bit = UINT_BIT_SIZE ; bit > 0 ; --bit )
    for ( Coord< size_t > c( 0, 0 ) ; c.y < codeBlock.spriteCount() * EBCOT_SPRITE_SIZE ; ++( c.y ) )
      for ( c.x = 0 ; c.x < codeBlock.width() ; ++( c.x ) )
        if ( GetBit( codeBlock[c].coeff, bit - 1 ) ) return( bit );

  return( 0 );
}

/*
  EBCOT符号/復号化メインルーチン

  codeBlock : コードブロックへのポインタ
  subband : サブバンド
  bit_size : 符号化するビット数 ( 最上位ビット + 1 )
  lsb : 符号化する最下位ビット( 0 で前ビットが対象 )
  lsbPass : 最下位ビットで実行するパス
    EBCOT_SP_PASS ... Significance Propagation Pass まで
    EBCOT_MR_PASS ... Magnitude Refinement Pass まで
    それ以外(EBCOT_CU_PASS) ... Cleanup Pass まで (全て対象)
  runlength : Runlength Coding function
  sigPro : Significance Coding function
  sign : Sign Coding function
  magRef : Magnitude Refinement Coding function
  coder : 符号化・復号化処理用関数オブジェクト
*/
template< class Runlength, class SigPro, class Sign, class MagRef, class Coder >
void EbcotMain( CodeBlock* codeBlock, unsigned int subband, unsigned int bit_size, unsigned int lsb, unsigned int lsbPass,
                Runlength runlength, SigPro sigPro, Sign sign, MagRef magRef, Coder& coder )
{
  // 最上位ビットは CleanupPass のみ
  CleanupPass( codeBlock, subband, bit_size, runlength, sigPro, sign, coder );
  // 中間ビット
  while ( bit_size > lsb + 1 ) {
    --bit_size;
    SigProPass( codeBlock, subband, bit_size, sigPro, sign, coder );
    MagRefPass( codeBlock, bit_size, magRef, coder );
    CleanupPass( codeBlock, subband, bit_size, runlength, sigPro, sign, coder );
  }
  // 最下位ビットに対しては途中のパスまでの可能性あり
  SigProPass( codeBlock, subband, lsb, sigPro, sign, coder );
  if ( lsbPass == EBCOT_SP_PASS ) return;
  MagRefPass( codeBlock, lsb, magRef, coder );
  if ( lsbPass == EBCOT_MR_PASS ) return;
  CleanupPass( codeBlock, subband, lsb, runlength, sigPro, sign, coder );
}

/*********************************************************
  インターフェース群
*********************************************************/

/*
  ビットプレーンの初期化

  サイズが 2 pixel 分大きいのは隣接するピクセルがCode Blockの外部にある場合を考慮している。
  そのため、Code Blockの左端は(1,1)から始まる。

  size : 係数のサイズ ( Y はスプライト数ではなくビット数を表す )
*/
void CodeBlock::init( Coord< size_t > size )
{
  // Y サイズをスプライト数に変更する
  size_t y = size.y / EBCOT_SPRITE_SIZE;
  // 余剰分を加算する
  if ( size.y % EBCOT_SPRITE_SIZE != 0 )
    ++y;

  bitPlane_.assign( ( size.x + 2 ) * ( y * EBCOT_SPRITE_SIZE + 2 ), BitPlane() );
  size_ = size;
  spriteCount_ = y;
}
void CodeBlock::init()
{ init( size_ ); }

/*
  Code Blockの初期化と、係数列からのデータ取り込み

  coeff : 係数列への参照
  coefSize : 係数列の大きさ
  block : 係数列上で符号化/復号化を行う位置
  blockSize : コードブロックの大きさ
*/
template< class T >
void CodeBlock::assign( const vector< T >& coeff, Coord< size_t > coefSize, Coord< size_t > block, Coord< size_t > blockSize )
{
  if ( block.x >= coefSize.x || block.y >= coefSize.y )
    throw std::out_of_range( "CodeBlock::assign : Block coord is out of coeff size." );

  Coord< size_t > codeBlockSize( blockSize ); // 確保するサイズ

  // 確保するエリアが係数列の範囲外にはみ出ている場合はサイズを補正
  if ( block.x + blockSize.x > coefSize.x )
    codeBlockSize.x = coefSize.x - block.x;
  if ( block.y + blockSize.y > coefSize.y )
    codeBlockSize.y = coefSize.y - block.y;
  init( codeBlockSize );

  for ( Coord< size_t > c( 0, 0 ) ; c.y < height() ; ++( c.y ) ) {
    size_t ty = block.y + c.y;
    for ( c.x = 0 ; c.x < width() ; ++( c.x ) ) {
      size_t tx = block.x + c.x;
      T t = coeff.at( ty * coefSize.x + tx );
      (*this)[c].coeff = abs( round( t ) );
      (*this)[c].isPos = ( t > 0 );
    }
  }
}
template void CodeBlock::assign( const vector< double >& coeff, Coord< size_t > coefSize, Coord< size_t > block, Coord< size_t > blockSize );
template void CodeBlock::assign( const vector< int >& coeff, Coord< size_t > coefSize, Coord< size_t > block, Coord< size_t > blockSize );

/*
  Code Blockの係数列への取得

  coeff : 係数列へのポインタ
  coefSize : 係数列の大きさ
  block : 係数列上で符号化/復号化を行った位置
*/
template< class T >
void CodeBlock::get( vector< T >* coeff, Coord< size_t > coefSize, Coord< size_t > block )
{
  for ( Coord< size_t > c( 0, 0 ) ; c.y < height() ; ++( c.y ) ) {
    size_t ty = block.y + c.y;
    if ( ty >= coefSize.y )
      throw std::out_of_range( "CodeBlock::get : Block coord is out of coeff size." );
    for ( c.x = 0 ; c.x < width() ; ++( c.x ) ) {
      size_t tx = block.x + c.x;
      if ( tx >= coefSize.x )
        throw std::out_of_range( "CodeBlock::get : Block coord is out of coeff size." );
      T t = (*this)[c].coeff;
      if ( ! (*this)[c].isPos ) t *= -1;
      coeff->at( ty * coefSize.x + tx ) = t;
    }
  }
}
template void CodeBlock::get( vector< double >* coeff, Coord< size_t > coefSize, Coord< size_t > block );
template void CodeBlock::get( vector< int >* coeff, Coord< size_t > coefSize, Coord< size_t > block );

/*
  EBCOT符号化メインルーチン

  subband : サブバンド
  lsb : 符号化する最下位ビット( 0 で前ビットが対象 )
  lsbPass : 最下位ビットで実行するパス
    EBCOT_SP_PASS ... Significance Propagation Pass まで
    EBCOT_MR_PASS ... Magnitude Refinement Pass まで
    それ以外(EBCOT_CU_PASS) ... Cleanup Pass まで (全て対象)
  encoder : 符号化処理用関数オブジェクト
*/
void CodeBlock::ebcotEncoder( unsigned int subband, unsigned int lsb, unsigned int lsbPass, Encoder& encoder )
{
  unsigned int bit_size = GetSignificantBitPlane( *this );

  // 最上位ビット位置 + 1 ( 0-255 ; 8bits ) を符号化
  for ( int i = EBCOT_BITSIZE_BIT - 1 ; i >= 0 ; --i ) {
    bool b = ( ( bit_size >> i ) & 1 ) != 0;
    encoder( b, CL_UNIFORM );
  }

  // サイズ ( 0 - 8191 ; 12bits )を符号化
  for ( int i = EBCOT_BLOCKSIZE_BIT - 1 ; i >= 0 ; --i ) {
    bool b = ( ( width() >> i ) & 1 ) != 0;
    encoder( b, CL_UNIFORM );
    b = ( ( height() >> i ) & 1 ) != 0;
    encoder( b, CL_UNIFORM );
  }

  if ( bit_size-- <= lsb ) return;

  EbcotMain( this, subband, bit_size, lsb, lsbPass,
             RunlengthEncode, SignificanceEncode, SignEncode, MR_Encode, encoder );
}

/*
  EBCOT復号化メインルーチン

  subband : サブバンド
  lsb : 符号化する最下位ビット( 0 で前ビットが対象 )
  lsbPass : 最下位ビットで実行するパス
    EBCOT_SP_PASS ... Significance Propagation Pass まで
    EBCOT_MR_PASS ... Magnitude Refinement Pass まで
    それ以外(EBCOT_CU_PASS) ... Cleanup Pass まで (全て対象)
  decoder : 復号化処理用関数オブジェクト
*/
void CodeBlock::ebcotDecoder( unsigned int subband, unsigned int lsb, unsigned int lsbPass, Decoder& decoder )
{
  // 最上位ビット位置 + 1 ( 0-255 ; 8bits ) を復号化
  unsigned int bit_size = 0;
  for ( int i = EBCOT_BITSIZE_BIT - 1 ; i >= 0 ; --i )
    bit_size = ( bit_size << 1 ) | ( ( decoder( CL_UNIFORM ) ) ? 1 : 0 );

  // サイズ ( 0 - 8191 ; 12bits )を復号化
  size_.x = size_.y = 0;
  for ( int i = EBCOT_BLOCKSIZE_BIT - 1 ; i >= 0 ; --i ) {
    size_.x = ( size_.x << 1 ) | ( ( decoder( CL_UNIFORM ) ) ? 1 : 0 );
    size_.y = ( size_.y << 1 ) | ( ( decoder( CL_UNIFORM ) ) ? 1 : 0 );
  }
  init();

  if ( bit_size-- <= lsb ) return;

  EbcotMain( this, subband, bit_size, lsb, lsbPass,
             RunlengthDecode, SignificanceDecode, SignDecode, MR_Decode, decoder );
}

/*
  初期値用定数
*/
enum MQ_INIT_PARAM
{
  // context label毎の Qe の index 初期値
  MQ_UNIFORM_INIT = 46,   // Uniform Context
  MQ_RUNLENGTH_INIT = 3,  // Run-length Coding
  MQ_SP_CODING0_INIT = 4, // context label = 0
  MQ_CONTEXT_INIT = 0,    // その他

  // MPS となる Decision の初期値
  MQ_MPS_INIT = false,

  // 確率区間(Range)の初期値
  MQ_RANGE_DECIMAL = 15,                 // Range の二進桁数 - 1
  MQ_RANGE_INIT = 1 << MQ_RANGE_DECIMAL, // Range 初期値
};

/*
  符号用パラメータ定数
*/
enum MQ_CODE_PARAM
{
  /*
    符号化用ビット数 0000 cbbb bbbb bsss xxxx xxxx xxxx xxxx
  */
  MQ_CODE_SIGN_BIT_COUNT = 16,         // fractional bits x
  MQ_CODE_SPACER_BIT_COUNT = 3,        // spacer bits s
  MQ_CODE_OUTPUT_BIT_COUNT = CHAR_BIT, // output bits b
  MQ_CODE_CARRY_BIT_COUNT = 1,         // carry bit c

  /*
    復号化用ビット数
     Chigh xxxx xxxx xxxx xxxx
     Clow  bbbb bbbb 0000 0000
  */
  MQ_CODE_CHIGH_BIT_COUNT = 16, // Chigh register
  MQ_CODE_CLOW_BIT_COUNT = 16,  // Clow register

  // Clow setのためのマスクパターン
  MQ_CODE_CLOW_MASK = ( 1 << MQ_CODE_CLOW_BIT_COUNT ) - 1,

  // 符号化用レジスタの符号長
  MQ_CODE_SIZE = MQ_CODE_SIGN_BIT_COUNT + MQ_CODE_SPACER_BIT_COUNT
  + MQ_CODE_OUTPUT_BIT_COUNT + MQ_CODE_CARRY_BIT_COUNT,

  // carry bit set のためのマスクパターン
  MQ_CODE_CARRY_SET = 1 << ( MQ_CODE_SIZE - MQ_CODE_CARRY_BIT_COUNT ),
  // carry bit reset のためのマスクパターン
  MQ_CODE_CARRY_RESET_MASK = MQ_CODE_CARRY_SET - 1,
};

/*
  Qeと状態遷移用構造体
*/
struct Qe_Type
{
  unsigned int Qe;   // Qe値
  unsigned int nmps; // MPS処理時の次のindex
  unsigned int nlps; // LPS処理時の次のindex
  unsigned int sw;   // 状態交換フラグ
};

/*
  Context Label毎の推定確率とMPS
*/
struct CL_Index_Type
{
  unsigned int index; // 状態遷移表のindex
  bool mps;           // MPSとなるDecision

  // コンストラクタ
  CL_Index_Type()
  : index( MQ_CONTEXT_INIT ), mps( MQ_MPS_INIT ) {}
};

/*
  MQ-Coder用のパラメータ
*/
struct MQ_Coder_Type
{
  unsigned int range;     // 確率区間
  unsigned int code;      // 符号
  unsigned int bit_count; // output bitsに登録されたビット数

  // コンストラクタ
  MQ_Coder_Type()
  : range( MQ_RANGE_INIT ), code( 0 ),
    bit_count( MQ_CODE_SPACER_BIT_COUNT + MQ_CODE_OUTPUT_BIT_COUNT + MQ_CODE_CARRY_BIT_COUNT ) {}
};

/*
  MQ-Coder 符号化関数オブジェクト
*/
class MQEncoder
{
  MQ_Coder_Type mqCoder_;                // MQ-Coder用のパラメータ
  std::vector< unsigned char >& out_;    // 符号出力先
  std::vector< CL_Index_Type > clIndex_; // Context Label毎の推定確率とMPS

  // 1 バイト出力
  void byteOutSub( unsigned int bitStuff );
  void byteOut();

  void renorme(); // 正規化処理

  void codeLPS( const Qe_Type& qe, CL_Index_Type* cl_index ); // LPS 符号化
  void codeMPS( const Qe_Type& qe, CL_Index_Type* cl_index ); // MPS 符号化

 public:

  // コンストラクタ
  MQEncoder( std::vector< unsigned char >& out );

  // デストラクタ(符号化の終端処理)
  ~MQEncoder() { flush(); }

  // 符号化の終端処理
  void flush();

  // 符号化処理
  void operator()( bool d, ContextLabel cl );
};

/*
  状態遷移表

  Qe値
  MPS処理時の次のindex
  LPS処理時の次のindex
  状態交換フラグ
*/
Qe_Type Qe[] = {

  { 0x5601,  1,  1, 1, }, { 0x3401,  2,  6, 0, }, { 0x1801,  3,  9, 0, }, { 0x0AC1,  4, 12, 0, },
  { 0x0521,  5, 29, 0, }, { 0x0221, 38, 33, 0, }, { 0x5601,  7,  6, 1, }, { 0x5401,  8, 14, 0, },
  { 0x4801,  9, 14, 0, }, { 0x3801, 10, 14, 0, }, { 0x3001, 11, 17, 0, }, { 0x2401, 12, 18, 0, },
  { 0x1C01, 13, 20, 0, }, { 0x1601, 29, 21, 0, },

  { 0x5601, 15, 14, 1, }, { 0x5401, 16, 14, 0, }, { 0x5101, 17, 15, 0, }, { 0x4801, 18, 16, 0, },
  { 0x3801, 19, 17, 0, }, { 0x3401, 20, 18, 0, }, { 0x3001, 21, 19, 0, }, { 0x2801, 22, 19, 0, },
  { 0x2401, 23, 20, 0, }, { 0x2201, 24, 21, 0, }, { 0x1C01, 25, 22, 0, }, { 0x1801, 26, 23, 0, },
  { 0x1601, 27, 24, 0, }, { 0x1401, 28, 25, 0, }, { 0x1201, 29, 26, 0, }, { 0x1101, 30, 27, 0, },
  { 0x0AC1, 31, 28, 0, }, { 0x09C1, 32, 29, 0, }, { 0x08A1, 33, 30, 0, }, { 0x0521, 34, 31, 0, },
  { 0x0441, 35, 32, 0, }, { 0x02A1, 36, 33, 0, }, { 0x0221, 37, 34, 0, }, { 0x0141, 38, 35, 0, },
  { 0x0111, 39, 36, 0, }, { 0x0085, 40, 37, 0, }, { 0x0049, 41, 38, 0, }, { 0x0025, 42, 39, 0, },
  { 0x0015, 43, 40, 0, }, { 0x0009, 44, 41, 0, }, { 0x0005, 45, 42, 0, }, { 0x0001, 45, 43, 0, },

  { 0x5601, 46, 46, 0, },
};

/*********************************************************
  符号化処理 内部ルーチン群
*********************************************************/

/*
  context label 毎の Qe の index を初期化する
*/
void InitCLIndex( vector< CL_Index_Type >* cp )
{
  (*cp)[CL_SP_CODING_0].index = MQ_SP_CODING0_INIT;     // 全近傍がゼロ
  (*cp)[CL_RUNLENGTH_CODING].index = MQ_RUNLENGTH_INIT; // Runlength
  (*cp)[CL_UNIFORM].index = MQ_UNIFORM_INIT;            // Uniform context
}

/*
  1 バイト出力する(サブ・ルーチン)

  bitStuff : Bit Stuffingを行うビット数 ( 0...行わない / 1...行う )
*/
void MQEncoder::byteOutSub( unsigned int bitStuff )
{
  /*
    cbbb bbbb bsss xxxx xxxx xxxx xxxx -> cbbb bbbb | bsss xxxx xxxx xxxx xxxx ( bitStuff = 1 )
                                       -> bbbb bbbb | 0sss xxxx xxxx xxxx xxxx ( bitStuff = 0 )
  */
  out_.push_back( mqCoder_.code >> ( MQ_CODE_SIGN_BIT_COUNT + MQ_CODE_SPACER_BIT_COUNT + bitStuff ) );
  mqCoder_.code &= ( 1 << ( MQ_CODE_SIGN_BIT_COUNT + MQ_CODE_SPACER_BIT_COUNT + bitStuff ) ) - 1;

  // Bit Stuffingを行った場合は次の出力までのカウントを一つ減らす
  mqCoder_.bit_count = MQ_CODE_OUTPUT_BIT_COUNT - bitStuff;
}

/*
  1 バイト出力する
*/
void MQEncoder::byteOut()
{
  if ( out_.size() == 0 ) {
    byteOutSub( 0 );
    return;
  }
  if ( out_.back() == 0xFF ) {
    byteOutSub( 1 );
    return;
  }

  // Carry bit がセットされている場合
  if ( mqCoder_.code >= 1 << ( MQ_CODE_SIZE - MQ_CODE_CARRY_BIT_COUNT ) ) {
    ++( out_.back() ); // 前の出力バイトに 1 を加える
    if ( out_.back() == 0xFF ) {
      // Carry Bit をリセットしてから Bit Stuffing
      mqCoder_.code &= MQ_CODE_CARRY_RESET_MASK;
      byteOutSub( 1 );
      return;
    }
  }

  byteOutSub( 0 );
}

/*
  符号化処理用の正規化処理
*/
void MQEncoder::renorme()
{
  do {
    mqCoder_.range <<= 1;
    mqCoder_.code <<= 1;
    --( mqCoder_.bit_count );

    if ( mqCoder_.bit_count == 0 )
      byteOut();
  } while( ( mqCoder_.range & MQ_RANGE_INIT ) == 0 );
}

/*
  LPSの符号化

  qe : 現在のContext Labelに対する状態遷移装置への参照 ( Qe[index[CL]] )
  clIndex : 現在の Context Label に対する index と MPS
*/
void MQEncoder::codeLPS( const Qe_Type& qe, CL_Index_Type* clIndex )
{
  mqCoder_.range -= qe.Qe; // Qe = LPS確率区間 ; Range - Qe = MPS確率区間

  if ( mqCoder_.range < qe.Qe ) {
    /*
      +-----LPS-----+--MPS--+
                    +-------+
    */
    mqCoder_.code += qe.Qe;
  } else {
    /*
      +--LPS--+-----MPS-----+
      +-------+
    */
    mqCoder_.range = qe.Qe;
  }
  if ( qe.sw == 1 )
    clIndex->mps = ! clIndex->mps;
  clIndex->index = qe.nlps;

  renorme();
}

/*
  MPSの符号化

  qe : 現在のContext Labelに対する状態遷移装置へのポインタ ( Qe[index[CL]] )
  clIndex : 現在の Context Label に対する index と MPS
*/
void MQEncoder::codeMPS( const Qe_Type& qe, CL_Index_Type* clIndex )
{
  mqCoder_.range -= qe.Qe; // Qe = LPS確率区間 ; Range - Qe = MPS確率区間

  // MPS < 0.75
  if ( ( mqCoder_.range & MQ_RANGE_INIT ) == 0 ) {
    if ( mqCoder_.range < qe.Qe ) {
      /*
        +-----LPS-----+--MPS--+
        +-------------+
      */
      mqCoder_.range = qe.Qe;
    } else {
      /*
        +--LPS--+-----MPS-----+
                +-------------+
      */
      mqCoder_.code += qe.Qe;
    }
    clIndex->index = qe.nmps;
    renorme();
    return;
  }

  /* MPS >= 0.75

    +--LPS--+-----MPS-----+
            +-------------+
  */
  mqCoder_.code += qe.Qe;
}

/*********************************************************
  符号化処理 インターフェース群
*********************************************************/

/*
  MEQncoder コンストラクタ

  out : 符号の出力先への参照
*/
MQEncoder::MQEncoder( std::vector< unsigned char >& out )
  : mqCoder_(), out_( out ), clIndex_( CL_SIZE )
{
  InitCLIndex( &clIndex_ );
}

/*
  符号化の終端処理
*/
void MQEncoder::flush()
{
  unsigned int temp = mqCoder_.code + mqCoder_.range;   // code + range = 確率区間の上限
  mqCoder_.code |= ( 1 << MQ_CODE_SIGN_BIT_COUNT ) - 1; // 符号ビット部分にできるだけ多く1をセットする

  // 確率区間の上限より大きい場合は、符号ビットの先頭ビットをOFFにする
  if ( mqCoder_.code >= temp ) mqCoder_.code -= MQ_RANGE_INIT;

  // 残りのOUTPUT BITを符号列に出力する
  for ( unsigned int i = 0 ; i < 3 ; i++ ) {
    mqCoder_.code <<= mqCoder_.bit_count;
    byteOut();
  }

  // 最後にゼロを出力(Bit Stuffing の伝播を防ぐため)
  out_.push_back( 0 );
}

/*
  MQ Coder符号化処理

  d : Decision
  cl : Context Label
*/
void MQEncoder::operator()( bool d, ContextLabel cl )
{
  CL_Index_Type* cp = &( clIndex_[cl] ); // 対象の Context Label の index と MPS

  if ( d == cp->mps ) {
    return( codeMPS( Qe[cp->index], cp ) );
  } else {
    return( codeLPS( Qe[cp->index], cp ) );
  }
}

/*
  MQ-Coder 復号化関数オブジェクト
*/
class MQDecoder
{
  MQ_Coder_Type mqCoder_;                            // MQ-Coder用のパラメータ
  std::vector< unsigned char >::const_iterator in_;  // 符号入力先
  std::vector< unsigned char >::const_iterator end_; // 符号列の末尾の次
  std::vector< CL_Index_Type > clIndex_;             // Context Label毎の推定確率とMPS
  unsigned int preVal_;                              // 前回に入力した値(Bit Stuffing確認用)

  // 1 バイト入力
  void byteInSub( unsigned int bit_stuff );
  void byteIn();

  void renormd(); // 正規化処理

  bool mpsExchange( const Qe_Type& qe, CL_Index_Type* cl_index ); // 復号器のMPSパス状態交換
  bool lpsExchange( const Qe_Type& qe, CL_Index_Type* cl_index ); // 復号器のLPSパス状態交換

 public:

  // コンストラクタ
  MQDecoder( std::vector< unsigned char >::const_iterator in, std::vector< unsigned char >::const_iterator end );

  // 復号化処理
  bool operator()( ContextLabel cl );
};

/*********************************************************
  復号化処理 内部ルーチン群
*********************************************************/

/*
  1 バイト入力する(サブ・ルーチン)

  bitStuff : Bit Stuffingを行うビット数(0...行わない/1...行う)
*/
void MQDecoder::byteInSub( unsigned int bitStuff )
{
  /*
    0000 0000 0000 0000 0000 0000 0000 0000 -> 0000 0000 0000 000b bbbb bbb0 0000 0000 ( bitStuff = 1 )
                                            -> 0000 0000 0000 0000 bbbb bbbb 0000 0000 ( bitStuff = 0 )
  */
  preVal_ = *in_++; // 前の値は Bit Stuffing 用に保持 ( 同時に char->int 型変換 )
  mqCoder_.code += preVal_ << ( MQ_CODE_CLOW_BIT_COUNT - MQ_CODE_OUTPUT_BIT_COUNT + bitStuff );

  // Bit Stuffingを行った場合は次の入力までのカウントを一つ減らす
  mqCoder_.bit_count = MQ_CODE_OUTPUT_BIT_COUNT - bitStuff;
}

/*
  1 バイト入力する
*/
void MQDecoder::byteIn()
{
  // 終端まで達した場合はそれ以上読み込まない
  if ( in_ == end_ )
    return;

  if ( preVal_ == 0xFF ) {
    byteInSub( 1 ); // Bit Stuffing を行う
  } else {
    byteInSub( 0 ); // Bit Stuffing を行わない
  }
}

/*
  復号化処理用の正規化処理
*/
void MQDecoder::renormd()
{
  do {
    if ( mqCoder_.bit_count == 0 )
      byteIn();
    mqCoder_.range <<= 1;
    mqCoder_.code <<= 1;
    mqCoder_.bit_count--;
  } while ( mqCoder_.range < MQ_RANGE_INIT );
}

/*
  復号器のMPSパス状態交換

  qe : 現在のContext Labelに対する状態遷移装置への参照 ( Qe[index[CL]] )
  clIndex : 現在のContext Labelに対するindexとMPS

  戻り値 : Decision
*/
bool MQDecoder::mpsExchange( const Qe_Type& qe, CL_Index_Type* clIndex )
{
  bool d; // Decision

  /*
    +-----LPS-----+--MPS--+  ->  D = LPS
  */
  if ( mqCoder_.range < qe.Qe ) {
    d = ! clIndex->mps;
    if ( qe.sw == 1 )
      clIndex->mps = ! clIndex->mps;
    clIndex->index = qe.nlps;
  }
  /*
    +--LPS--+-----MPS-----+  ->  D = MPS
  */
  else {
    d = clIndex->mps;
    clIndex->index = qe.nmps;
  }

  return( d );
}

/*
  復号器のLPSパス状態交換

  qe : 現在のContext Labelに対する状態遷移装置への参照 ( Qe[index[CL]] )
  clIndex : 現在のContext Labelに対するindexとMPS

  戻り値 : Decision
*/
bool MQDecoder::lpsExchange( const Qe_Type& qe, CL_Index_Type* clIndex )
{
  bool d; // Decision

  /*
    +-----LPS-----+--MPS--+  ->  D = MPS
  */
  if ( mqCoder_.range < qe.Qe ) {
    mqCoder_.range = qe.Qe;
    d = clIndex->mps;
    clIndex->index = qe.nmps;
  }
  /*
    +--LPS--+-----MPS-----+  ->  D = LPS
  */
  else {
    mqCoder_.range = qe.Qe;
    d = ! clIndex->mps;
    if ( qe.sw == 1 )
      clIndex->mps = ! clIndex->mps;
    clIndex->index = qe.nlps;
  }

  return( d );
}

/*********************************************************
  復号化処理 インターフェース群
*********************************************************/

/*
  復号化処理用の初期化

  [ in, end ) : 復号化する符号の先頭から末尾までの範囲
*/
MQDecoder::MQDecoder( vector< unsigned char >::const_iterator in, vector< unsigned char >::const_iterator end )
  : mqCoder_(), in_( in ), end_( end ), clIndex_( CL_SIZE ), preVal_( 0 )
{
  if ( in_ == end_ )
    throw std::out_of_range( "MQDecoder constructor : No more data for decode." );

  InitCLIndex( &clIndex_ );

  unsigned int code = *in_++; // char->int 型変換
  mqCoder_.code = code << MQ_CODE_CLOW_BIT_COUNT;
  byteIn();

  mqCoder_.code <<= ( MQ_RANGE_DECIMAL - MQ_CODE_OUTPUT_BIT_COUNT );
  mqCoder_.bit_count -= MQ_RANGE_DECIMAL - MQ_CODE_OUTPUT_BIT_COUNT;
  mqCoder_.range = MQ_RANGE_INIT;
}

/*
  MQ Coder復号化処理

  cl : Context Label

  戻り値 : Decision
*/
bool MQDecoder::operator()( ContextLabel cl )
{
  bool d; // Decision
  CL_Index_Type* cp = &( clIndex_[cl] );     // 対象の Context Label の index と MPS
  const Qe_Type& qe = Qe[cp->index];         // 対象の Context Label の推定確率と状態遷移
  unsigned int h_code = mqCoder_.code >> 16; // Chigh = 符号の上位16ビット

  mqCoder_.range -= qe.Qe; // Qe = LPS確率区間 ; Range - Qe = MPS確率区間
  /*
    Chigh
    +-+
    +--LPS--+-----MPS-----+
       ↓
    +-------+
    +-+
    Chigh
  */
  if ( h_code < qe.Qe ) {
    d = lpsExchange( qe, cp );
    renormd();
  }
  /*
             Chigh
    +----------+
    +--LPS--+-----MPS-----+
                  ↓
            +-------------+
            +--+
             Chigh
  */
  else {
    // ChighからLPS確率区間を引く
    mqCoder_.code -= qe.Qe << MQ_CODE_CLOW_BIT_COUNT;
    // A < 0.75ならMPS_EXCHANGEへ
    if ( ( mqCoder_.range & MQ_RANGE_INIT ) == 0 ) {
      d = mpsExchange( qe, cp );
      renormd();
    } else {
      d = cp->mps;
    }
  }

  return( d );
}

// 符号・復号化は MQ-Coder
typedef MQEncoder Encoder;
typedef MQDecoder Decoder;

Coord< int > destSize;                       // 画像サイズ(変換する回数に応じて余白を付加したサイズ)
vector< vector< WaveletCoef< T > > >wc( 3 ); // ウェーブレット変換結果
unsigned int level;        // ウェーブレット変換回数
vector< int > lsb( 3 );    // 符号化する最下位ビット(YUV各成分)
vector< int > pass( 3 );   // 最下位ビットに対する最終符号化パス(YUV各成分)
Coord< size_t > blockSize; // コードブロックの大きさ

// YUVへ変換
  :
// Wavelet 変換
  :

// EBCOT/MQ-Coder 符号化
vector< vector< unsigned char > > code( 3 ); // EBCOT 符号(YUV各成分)
vector< vector< size_t > > start( 3 );       // EBCOT 符号の開始位置(YUV各成分)

// YUV 各成分に対して実行
for ( size_t i = 0 ; i < code.size() ; ++i ) {
  Coord< size_t > sz( destSize ); // 係数のサイズ
  CodeBlock codeBlock;            // コードブロック
  Encoder* encoder = new Encoder( code[i] ); // --- (1)
  start[i].push_back( 0 ); // 最初はゼロからスタート
  for ( size_t j = 0 ; j < level ; ++j ) {
    sz.x >>= 1; sz.y >>= 1; // 係数はレベルごとに半分に
    // ウェーブレット係数(LH/HL/HH)
    for ( size_t y = 0 ; y < sz.y ; y += blockSize.y ) {
      for ( size_t x = 0 ; x < sz.x ; x += blockSize.x ) {
        //Encoder* encoder = new Encoder( code[i] ); // --- (2)
        codeBlock.assign( wc[i][j].wv, sz, Coord< size_t >( x, y ), blockSize );
        codeBlock.ebcotEncoder( EBCOT_SUBBAND_LH, lsb[i], pass[i], *encoder );
        codeBlock.assign( wc[i][j].wh, sz, Coord< size_t >( x, y ), blockSize );
        codeBlock.ebcotEncoder( EBCOT_SUBBAND_HL, lsb[i], pass[i], *encoder );
        codeBlock.assign( wc[i][j].wd, sz, Coord< size_t >( x, y ), blockSize );
        codeBlock.ebcotEncoder( EBCOT_SUBBAND_HH, lsb[i], pass[i], *encoder );
        //delete encoder; // --- (2)
        start[i].push_back( code[i].size() ); // 終端 = 次の開始位置
      }
    }
  }
  // スケーリング係数(LL)
  for ( size_t y = 0 ; y < sz.y ; y += blockSize.y ) {
    for ( size_t x = 0 ; x < sz.x ; x += blockSize.x ) {
      //Encoder* encoder = new Encoder( code[i] ); // --- (2)
      codeBlock.assign( wc[i][level - 1].s, sz, Coord< size_t >( x, y ), blockSize );
      codeBlock.ebcotEncoder( EBCOT_SUBBAND_LL, lsb[i], pass[i], *encoder );
      //delete encoder; // --- (2)
      start[i].push_back( code[i].size() ); // 終端 = 次の開始位置
    }
  }
  delete encoder; // --- (1)
}

// EBCOT/MQ-Coder 復号化
// YUV 各成分に対して実行
for ( size_t i = 0 ; i < code.size() ; ++i ) {
  size_t index = 0; // EBCOT 符号の開始位置を示す添字
  Coord< size_t > sz( destSize ); // 係数のサイズ
  CodeBlock codeBlock;            // コードブロック
  Decoder decoder( code[i].begin(), code[i].end() ); // --- (1)
  for ( size_t j = 0 ; j < level ; ++j ) {
    sz.x >>= 1; sz.y >>= 1;
    for ( size_t y = 0 ; y < sz.y ; y += blockSize.y ) {
      for ( size_t x = 0 ; x < sz.x ; x += blockSize.x ) {
        //Decoder decoder( code[i].begin() + start[i][index], code[i].begin() + start[i][index + 1] ); // ---(2)
        codeBlock.ebcotDecoder( EBCOT_SUBBAND_LH, lsb[i], pass[i], decoder );
        codeBlock.get( &( wc[i][j].wv ), sz, Coord< size_t >( x, y ) );
        codeBlock.ebcotDecoder( EBCOT_SUBBAND_HL, lsb[i], pass[i], decoder );
        codeBlock.get( &( wc[i][j].wh ), sz, Coord< size_t >( x, y ) );
        codeBlock.ebcotDecoder( EBCOT_SUBBAND_HH, lsb[i], pass[i], decoder );
        codeBlock.get( &( wc[i][j].wd ), sz, Coord< size_t >( x, y ) );
        ++index;
      }
    }
  }
  for ( size_t y = 0 ; y < sz.y ; y += blockSize.y ) {
    for ( size_t x = 0 ; x < sz.x ; x += blockSize.x ) {
      //Decoder decoder( code[i].begin() + start[i][index], code[i].begin() + start[i][index + 1] ); // --- (2)
      codeBlock.ebcotDecoder( EBCOT_SUBBAND_LL, lsb[i], pass[i], decoder );
      codeBlock.get( &( wc[i][level - 1].s ), sz, Coord< size_t >( x, y ) );
      ++index;
    }
  }
}

// Wavelet 逆変換
  :
// 画像へ変換
  :