JPEGを読む(8) RECEIVEとEXTEND

　ハフマン符号の復号はいいけど、その後のデータを読む部分を忘れていた。(3)のRECEIVEとEXTENDについて。

RECEIVE(SSSS)

　SSSSビットを読み取る処理。自明かと思ったけどちゃんと説明されていたので一応読む。SSSSというのは4ビットの数値というだけで特に意味があるわけではない。

　1ビット読み取る関数NEXTBITがあって、特筆することはない。コードは以下。

func (d *Decoder) receive(l int) (uint8, error) {
    var ret uint8
    for i := 0; i < l; i++ {
        b, err := d.nextBit()
        if err != nil {
            return 0, err
        }

        ret = ret<<1 + uint8(b)
    }

    return ret, nil
}

NEXTBIT

　NEXTBITも細かい解説がある。

　変数CNTとBに状態を保存してある。基本的には1バイトずつ読み取ってBに保存しておき、そこからNEXTBITを呼び出される度に1ビットずつシフトして取り出していく。8回読み終えると次の1バイトを読む。読んだ1バイトがDNLマーカーだった場合はスキャンを終了する。ついでなのでDNLの読み取りも実装するとこうなる。

type Decoder struct {
// ...

    bitMask uint8
    bits    uint8 
    numLine uint16
}

import "errors"

var (
    EOS = errors.New("end of scan")
)

func (d *Decoder) readDNL() (uint16, error) {
    ld, err := d.readUint16()
    if err != nil {
        return 0, err 
    }   

    if ld != 4 { 
        return 0, errors.New("Unexpected NDL length")
    }   

    return d.readUint16()
}

func (d *Decoder) nextBit() (uint16, error) {
    if d.bitMask == 0 { 
        b, err := d.readUint8()
        if err == ErrUnexpectedMarker {
            d.unread()
            m, err := d.readMarker()
            if err != nil {
                return 0, err 
            }

            if m == Marker_DNL {
                l, err := d.readDNL()
                if err != nil {
                    return 0, err 
                }

                d.numLine = l 

                return 0, EOS 
            }

            return 0, ErrUnexpectedMarker
        } else if err != nil {
            return 0, err
        }

        d.bits = b
        d.bitMask = 0b1000_0000
    }

    bitMask := d.bitMask
    d.bitMask >>= 1
    if d.bits&bitMask == 0 {
        return 0b0, nil
    } else {
        return 0b1, nil
    }
}

　CNTだとピンとこなかったのでビットマスクで表現した。スキャンの終了はエラー値を定義して表現することにした。あとは以前に実装したDecoder#readUint8とDecoder#readMarker, Decoder#unreadで簡単に実装できる。

　DNLの意味は一旦置いておく。

EXTEND(V, T)

　EXTENDは、RECEIVEで読み取った値を符号つき整数に変換する処理となる。VはRECEIVEの戻り値で、TはRECEIVEの引数となっている。

　フローチャートの通りに実装することは簡単だけど、このフローチャートの意味がよくわからない。というのはつまり正負の符号を含む値の表現方法を理解していないということになる。説明はF.1.2.1節とTable F.1にある。

　ここでSSSSはRECEIVEの引数で、読み取ったビット数Tのこと。DIFFはRECEIVEで読み取った値Vのこととなる。

　SSSS = 0の場合、ストリームを読み取ることなくそのまま0となる。

　SSSS = 1 の場合、つまり1ビット読み取った場合、1ビットには -1, 1 という2つの値が割り当てられている。これを小さい順に符号に割り当てる。

T	V	value
1	0₂	-1
1	1₂	1

　SSSS = 2 の場合、2ビットには -3, -2, 2, 3 という4つの値が割り当てられているので、これを小さい順に符号に割り当てる。

T	V	value
2	00₂	-3
2	01₂	-2
2	10₂	2
2	11₂	3

　以下同じ。

　これをアルゴリズムで表すとFigure F.12のフローチャートになる。表を見ると正の数の時 = 最上位ビットが1の時 = V < 2^T-1でない時、戻り値はVの値そのままになっていることがわかる。

　このように数値をコード化している理由は、0もしくは絶対値が小さい値の出現確率が極端に多く、かつ表現する値域が広いためハフマン符号化するとテーブルが大きくなりすぎるためだと思われる。差分符号化なので絶対値が小さい値が多いのだろう。

　実装は以下のようにした。ほぼフローチャートのまま。

func extend(v_ uint8, t int) int16 {
    var v int16 = int16(v_)
    var vt int16 = 1 << (t - 1)
    if v < vt {
        return v + (-1 << t) + 1 
    }   
    return v
}

yunomuのブログ

趣味のこと

JPEGを読む(8) RECEIVEとEXTEND

RECEIVE(SSSS)

NEXTBIT

EXTEND(V, T)