enArith  算術符号
deArith  算術符号からの復号

算術符号
    long enArith(unsigned char *code, long clen,
                 unsigned char *text, long tlen);

算術符号からの復号
    long deArith(unsigned char *text, long tlen,
                 unsigned char *code, long clen);

算術符号関数において
    code  （入出力）算術符号を格納する配列
    clen  （入力）  配列codeの長さ
    text  （入力）  テキストを格納する配列
    tlen  （入力）  配列textの長さ

算術符号からの復号関数において
    text  （入出力）テキストを格納する配列
    tlen  （入力）  配列textの長さ
    code  （入力）  算術符号を格納する配列
    clen  （入力）  配列codeの長さ

算術符号関数について
    算術符号の長さ。符号化に失敗したときは -1L。

算術符号からの復号関数について
    テキストの長さ。復号に失敗したときは -1L。

#define CHAR_SIZE    256      /* 文字種類 */

#define Q      0xffffffffL
#define Q1     0x40000000L
#define Q2     0x80000000L
#define Q3     0xC0000000L

long enArith(unsigned char *code, long clen,unsigned char *text, long tlen){


    int    i, k;
    long   c, len;
    int    comp;
    long   max;
    long   sum, t;
    long   count[CHAR_SIZE+2];
    unsigned long  L, R, q, r;
    long outbit();

    if (tlen <= 0 || clen <= 2*CHAR_SIZE) 

        return -1L;

    /* 各文字の出現頻度を計算 */
    for (i = 0; i < CHAR_SIZE; i++) 

        count[i] = 0;
    for (c = 0; c < tlen; c++) 

        count[text[c]]++;

    /* 最大出現頻度の値が２バイトを越えないように調整する */
    for (i = 0, max = 0; i < CHAR_SIZE; i++)
        if (count[i] > max) max = count[i];
    if ((k = max/0x10000L) > 0)
        for (i = 0, k++; i < CHAR_SIZE; i++)
            if (count[i] > 0) {
                count[i] /= k;
                if (count[i] == 0) 

                    count[i] = 1;
            }

    /* 各文字の出現頻度を出力 */
    for (i = 0, len = 0; i < CHAR_SIZE; i++) {
        code[len++] = (count[i] >> 8) & 0xff;
        code[len++] = count[i] & 0xff;
    }
    
    /* EOF */
    count[CHAR_SIZE] = 1;

    /* 累積頻度に直す */
    t = count[0];
    count[0] = 0;
    for (i = 1; i <= CHAR_SIZE+1; i++) {
        long tmp = count[i];
        count[i] = count[i-1] + t;
        t = tmp;
    }
    sum = count[CHAR_SIZE+1];

    /* 各文字を符号化 */
    L = 0; R = Q;
    for (c = 0, comp = 0, i = 0; ; c++) {
        k = (c == tlen) ? CHAR_SIZE : text[c];
        
        /* 区間を更新 */
        q = (R - L) / sum;
        r = (R - L) % sum;
        R = L + q*count[k+1] + (r*count[k+1])/sum - 1;
        L = L + q*count[k]   + (r*count[k])  /sum + 1; 
        
        /* ビットを出力 */
        while (R - L <= Q1) {
            if (R < Q2) {
                len = outbit(0, code, len, comp, &i);
                if (len > clen) return -1L;
                comp = 0;
            } else if (L >= Q2) {
                len = outbit(1, code, len, comp, &i);
                if (len > clen) return -1L;
                comp = 0;
                L -= Q2; R -= Q2;
            } else if (Q1 <= L && R < Q3) {
                comp++;
                L -= Q1; R -= Q1;
            }
            L <<= 1; R <<= 1;
        }
        if (k == CHAR_SIZE) break;
    }
    if (L <= Q1) {
        len = outbit(0, code, len, comp, &i);
        len = outbit(1, code, len, 0,    &i);
    } else if (L <= Q2) {
        len = outbit(1, code, len, comp, &i);
        len = outbit(0, code, len, 0,    &i);
    } else {
        len = outbit(1, code, len, comp, &i);
        len = outbit(1, code, len, 0,    &i);
    }
    if (i > 0) {
        while (i > 0) outbit(0, code, len, 0, &i);
        len++;
    }
    return (len > clen) ? -1L : len;
}

static long outbit(int bit, unsigned char *code, long len,
                   int comp, int *i)
{
    static unsigned char bit0[8] = {~128,~64,~32,~16,~8,~4,~2,~1};
    static unsigned char bit1[8] = { 128, 64, 32, 16, 8, 4, 2, 1};
    
    if (bit) code[len] |= bit1[*i];
    else     code[len] &= bit0[*i];
    if (++(*i) == 8) {
        len++;
        *i = 0;
    }
    while (comp--) {
        if (bit) code[len] &= bit0[*i];
        else     code[len] |= bit1[*i];
        if (++(*i) == 8) {
            len++;
            *i = 0;
        }
    }
    return len;
}

long deArith(unsigned char *text, long tlen,
             unsigned char *code, long clen)
{
    unsigned char c;
    int    i, k;
    long   j, len;
    long   sum, t;
    long   count[CHAR_SIZE+2];
    unsigned long  L, R, V, q, r;
    static unsigned char bit1[8] = {128,64,32,16,8,4,2,1};

    if (clen <= 2*CHAR_SIZE) return -1L;

    /* 各文字の出現頻度をセット */
    for (i = 0; i < CHAR_SIZE; i++) count[i] = 0;
    for (i = 0; i < CHAR_SIZE; i++) {
        count[i] = *code++;
        count[i] = (count[i] << 8) | *code++;
    }
    
    /* EOF */
    count[CHAR_SIZE] = 1;

    /* 累積頻度に直す */
    t = count[0];
    count[0] = 0;
    for (i = 1; i <= CHAR_SIZE+1; i++) {
        long tmp = count[i];
        count[i] = count[i-1] + t;
        t = tmp;
    }
    sum = count[CHAR_SIZE+1];

    /* 復号化 */
    L = 0; R = Q; V = 0;
    for (i = 0, j = 2*CHAR_SIZE; i < 4; i++) {
        V <<= 8;
        if (j++ < clen) V |= *code++;
    }
    c = (j <= clen) ? *code : 0;

    for (i = 0, len = 0; ; ) {
        /* 区間を更新 */
        q = (R - L) / sum;
        r = (R - L) % sum;
        for (k = 0; k <= CHAR_SIZE; k++) {
            R = L + q*count[k+1] + (r*count[k+1])/sum;
            if (R > 0 && --R >= V) break;
        }
        L = L + q*count[k] + (r*count[k])/sum + 1; 
        
        if (k == CHAR_SIZE) break;
        *text++ = k;
        if (++len > clen) return -1L;
        
        /* 区間のシフト */
        while (R - L <= Q1) {
            if (R < Q2) ;
            else if (L >= Q2) {
                L -= Q2; R -= Q2; V -= Q2;
            } else if (Q1 <= L && R < Q3) {
                L -= Q1; R -= Q1; V -= Q1;
            }
            L <<= 1; R <<= 1; V <<= 1;
            if (c & bit1[i]) V |= 1;
            if (++i == 8) {
                c = (j++ <= clen) ? *++code : 0;
                i = 0;
            }
        }
    }
    return len;
}

算術符号は幅広く研究がなされるようになったのは1970年代の後半であり、 一般にはあまり知られていないのが現状である。

算術符号は理論上、平均符号長がエントロピーとなる。つまり、平均符号長に 関しては、算術符号は最適符号である。これに対して、よく知られている ハフマン符号はその平均符号長は必ずしも エントロピーにならない。しかし算術符号においては、符号化の際、無限桁の 実数演算が理論上必要となるので、実用上有限桁の整数で近似する工夫が必要 であろう。

算術符号は入力記号（文字）の出現確率に基づいて単位区間 [0, 1)（左端が0 を含み、右端が1を含まない区間）を逐次縮小し、最終的に得られた区間内の 値を符号とする符号である。ハフマン符号では出現確率の大きい記号に短い 符号語を割り当てるのに対して、算術符号では、出現確率の大きい文字に幅の 大きい区間を振り分ける。