URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [image/] [jpeg/] [huffman.go] - Blame information for rev 747

Details | Compare with Previous | View Log


// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
 
package jpeg
 
import "io"
 
// Each code is at most 16 bits long.
const maxCodeLength = 16
 
// Each decoded value is a uint8, so there are at most 256 such values.
const maxNumValues = 256
 
// Bit stream for the Huffman decoder.
// The n least significant bits of a form the unread bits, to be read in MSB to LSB order.
type bits struct {
        a int // accumulator.
        n int // the number of unread bits in a.
        m int // mask. m==1<<(n-1) when n>0, with m==0 when n==0.
}
 
// Huffman table decoder, specified in section C.
type huffman struct {
        l        [maxCodeLength]int
        length   int                 // sum of l[i].
        val      [maxNumValues]uint8 // the decoded values, as sorted by their encoding.
        size     [maxNumValues]int   // size[i] is the number of bits to encode val[i].
        code     [maxNumValues]int   // code[i] is the encoding of val[i].
        minCode  [maxCodeLength]int  // min codes of length i, or -1 if no codes of that length.
        maxCode  [maxCodeLength]int  // max codes of length i, or -1 if no codes of that length.
        valIndex [maxCodeLength]int  // index into val of minCode[i].
}
 
// Reads bytes from the io.Reader to ensure that bits.n is at least n.
func (d *decoder) ensureNBits(n int) error {
        for d.b.n < n {
                c, err := d.r.ReadByte()
                if err != nil {
                        return err
                }
                d.b.a = d.b.a<<8 | int(c)
                d.b.n += 8
                if d.b.m == 0 {
                        d.b.m = 1 << 7
                } else {
                        d.b.m <<= 8
                }
                // Byte stuffing, specified in section F.1.2.3.
                if c == 0xff {
                        c, err = d.r.ReadByte()
                        if err != nil {
                                return err
                        }
                        if c != 0x00 {
                                return FormatError("missing 0xff00 sequence")
                        }
                }
        }
        return nil
}
 
// The composition of RECEIVE and EXTEND, specified in section F.2.2.1.
func (d *decoder) receiveExtend(t uint8) (int, error) {
        err := d.ensureNBits(int(t))
        if err != nil {
                return 0, err
        }
        d.b.n -= int(t)
        d.b.m >>= t
        s := 1 << t
        x := (d.b.a >> uint8(d.b.n)) & (s - 1)
        if x < s>>1 {
                x += ((-1) << t) + 1
        }
        return x, nil
}
 
// Processes a Define Huffman Table marker, and initializes a huffman struct from its contents.
// Specified in section B.2.4.2.
func (d *decoder) processDHT(n int) error {
        for n > 0 {
                if n < 17 {
                        return FormatError("DHT has wrong length")
                }
                _, err := io.ReadFull(d.r, d.tmp[0:17])
                if err != nil {
                        return err
                }
                tc := d.tmp[0] >> 4
                if tc > maxTc {
                        return FormatError("bad Tc value")
                }
                th := d.tmp[0] & 0x0f
                const isBaseline = true // Progressive mode is not yet supported.
                if th > maxTh || isBaseline && th > 1 {
                        return FormatError("bad Th value")
                }
                h := &d.huff[tc][th]
 
                // Read l and val (and derive length).
                h.length = 0
                for i := 0; i < maxCodeLength; i++ {
                        h.l[i] = int(d.tmp[i+1])
                        h.length += h.l[i]
                }
                if h.length == 0 {
                        return FormatError("Huffman table has zero length")
                }
                if h.length > maxNumValues {
                        return FormatError("Huffman table has excessive length")
                }
                n -= h.length + 17
                if n < 0 {
                        return FormatError("DHT has wrong length")
                }
                _, err = io.ReadFull(d.r, h.val[0:h.length])
                if err != nil {
                        return err
                }
 
                // Derive size.
                k := 0
                for i := 0; i < maxCodeLength; i++ {
                        for j := 0; j < h.l[i]; j++ {
                                h.size[k] = i + 1
                                k++
                        }
                }
 
                // Derive code.
                code := 0
                size := h.size[0]
                for i := 0; i < h.length; i++ {
                        if size != h.size[i] {
                                code <<= uint8(h.size[i] - size)
                                size = h.size[i]
                        }
                        h.code[i] = code
                        code++
                }
 
                // Derive minCode, maxCode, and valIndex.
                k = 0
                index := 0
                for i := 0; i < maxCodeLength; i++ {
                        if h.l[i] == 0 {
                                h.minCode[i] = -1
                                h.maxCode[i] = -1
                                h.valIndex[i] = -1
                        } else {
                                h.minCode[i] = k
                                h.maxCode[i] = k + h.l[i] - 1
                                h.valIndex[i] = index
                                k += h.l[i]
                                index += h.l[i]
                        }
                        k <<= 1
                }
        }
        return nil
}
 
// Returns the next Huffman-coded value from the bit stream, decoded according to h.
// TODO(nigeltao): This decoding algorithm is simple, but slow. A lookahead table, instead of always
// peeling off only 1 bit at at time, ought to be faster.
func (d *decoder) decodeHuffman(h *huffman) (uint8, error) {
        if h.length == 0 {
                return 0, FormatError("uninitialized Huffman table")
        }
        for i, code := 0, 0; i < maxCodeLength; i++ {
                err := d.ensureNBits(1)
                if err != nil {
                        return 0, err
                }
                if d.b.a&d.b.m != 0 {
                        code |= 1
                }
                d.b.n--
                d.b.m >>= 1
                if code <= h.maxCode[i] {
                        return h.val[h.valIndex[i]+code-h.minCode[i]], nil
                }
                code <<= 1
        }
        return 0, FormatError("bad Huffman code")
}

Line No.	Rev	Author	Line
1	747	jeremybenn	`// Copyright 2009 The Go Authors. All rights reserved.`
2			`// Use of this source code is governed by a BSD-style`
3			`// license that can be found in the LICENSE file.`
4
5			`package jpeg`
6
7			`import "io"`
8
9			`// Each code is at most 16 bits long.`
10			`const maxCodeLength = 16`
11
12			`// Each decoded value is a uint8, so there are at most 256 such values.`
13			`const maxNumValues = 256`
14
15			`// Bit stream for the Huffman decoder.`
16			`// The n least significant bits of a form the unread bits, to be read in MSB to LSB order.`
17			`type bits struct {`
18			`a int // accumulator.`
19			`n int // the number of unread bits in a.`
20			`m int // mask. m==1<<(n-1) when n>0, with m==0 when n==0.`
21			`}`
22
23			`// Huffman table decoder, specified in section C.`
24			`type huffman struct {`
25			`l [maxCodeLength]int`
26			`length int // sum of l[i].`
27			`val [maxNumValues]uint8 // the decoded values, as sorted by their encoding.`
28			`size [maxNumValues]int // size[i] is the number of bits to encode val[i].`
29			`code [maxNumValues]int // code[i] is the encoding of val[i].`
30			`minCode [maxCodeLength]int // min codes of length i, or -1 if no codes of that length.`
31			`maxCode [maxCodeLength]int // max codes of length i, or -1 if no codes of that length.`
32			`valIndex [maxCodeLength]int // index into val of minCode[i].`
33			`}`
34
35			`// Reads bytes from the io.Reader to ensure that bits.n is at least n.`
36			`func (d *decoder) ensureNBits(n int) error {`
37			`for d.b.n < n {`
38			`c, err := d.r.ReadByte()`
39			`if err != nil {`
40			`return err`
41			`}`
42			`d.b.a = d.b.a<<8 \| int(c)`
43			`d.b.n += 8`
44			`if d.b.m == 0 {`
45			`d.b.m = 1 << 7`
46			`} else {`
47			`d.b.m <<= 8`
48			`}`
49			`// Byte stuffing, specified in section F.1.2.3.`
50			`if c == 0xff {`
51			`c, err = d.r.ReadByte()`
52			`if err != nil {`
53			`return err`
54			`}`
55			`if c != 0x00 {`
56			`return FormatError("missing 0xff00 sequence")`
57			`}`
58			`}`
59			`}`
60			`return nil`
61			`}`
62
63			`// The composition of RECEIVE and EXTEND, specified in section F.2.2.1.`
64			`func (d *decoder) receiveExtend(t uint8) (int, error) {`
65			`err := d.ensureNBits(int(t))`
66			`if err != nil {`
67			`return 0, err`
68			`}`
69			`d.b.n -= int(t)`
70			`d.b.m >>= t`
71			`s := 1 << t`
72			`x := (d.b.a >> uint8(d.b.n)) & (s - 1)`
73			`if x < s>>1 {`
74			`x += ((-1) << t) + 1`
75			`}`
76			`return x, nil`
77			`}`
78
79			`// Processes a Define Huffman Table marker, and initializes a huffman struct from its contents.`
80			`// Specified in section B.2.4.2.`
81			`func (d *decoder) processDHT(n int) error {`
82			`for n > 0 {`
83			`if n < 17 {`
84			`return FormatError("DHT has wrong length")`
85			`}`
86			`_, err := io.ReadFull(d.r, d.tmp[0:17])`
87			`if err != nil {`
88			`return err`
89			`}`
90			`tc := d.tmp[0] >> 4`
91			`if tc > maxTc {`
92			`return FormatError("bad Tc value")`
93			`}`
94			`th := d.tmp[0] & 0x0f`
95			`const isBaseline = true // Progressive mode is not yet supported.`
96			`if th > maxTh \|\| isBaseline && th > 1 {`
97			`return FormatError("bad Th value")`
98			`}`
99			`h := &d.huff[tc][th]`
100
101			`// Read l and val (and derive length).`
102			`h.length = 0`
103			`for i := 0; i < maxCodeLength; i++ {`
104			`h.l[i] = int(d.tmp[i+1])`
105			`h.length += h.l[i]`
106			`}`
107			`if h.length == 0 {`
108			`return FormatError("Huffman table has zero length")`
109			`}`
110			`if h.length > maxNumValues {`
111			`return FormatError("Huffman table has excessive length")`
112			`}`
113			`n -= h.length + 17`
114			`if n < 0 {`
115			`return FormatError("DHT has wrong length")`
116			`}`
117			`_, err = io.ReadFull(d.r, h.val[0:h.length])`
118			`if err != nil {`
119			`return err`
120			`}`
121
122			`// Derive size.`
123			`k := 0`
124			`for i := 0; i < maxCodeLength; i++ {`
125			`for j := 0; j < h.l[i]; j++ {`
126			`h.size[k] = i + 1`
127			`k++`
128			`}`
129			`}`
130
131			`// Derive code.`
132			`code := 0`
133			`size := h.size[0]`
134			`for i := 0; i < h.length; i++ {`
135			`if size != h.size[i] {`
136			`code <<= uint8(h.size[i] - size)`
137			`size = h.size[i]`
138			`}`
139			`h.code[i] = code`
140			`code++`
141			`}`
142
143			`// Derive minCode, maxCode, and valIndex.`
144			`k = 0`
145			`index := 0`
146			`for i := 0; i < maxCodeLength; i++ {`
147			`if h.l[i] == 0 {`
148			`h.minCode[i] = -1`
149			`h.maxCode[i] = -1`
150			`h.valIndex[i] = -1`
151			`} else {`
152			`h.minCode[i] = k`
153			`h.maxCode[i] = k + h.l[i] - 1`
154			`h.valIndex[i] = index`
155			`k += h.l[i]`
156			`index += h.l[i]`
157			`}`
158			`k <<= 1`
159			`}`
160			`}`
161			`return nil`
162			`}`
163
164			`// Returns the next Huffman-coded value from the bit stream, decoded according to h.`
165			`// TODO(nigeltao): This decoding algorithm is simple, but slow. A lookahead table, instead of always`
166			`// peeling off only 1 bit at at time, ought to be faster.`
167			`func (d decoder) decodeHuffman(h huffman) (uint8, error) {`
168			`if h.length == 0 {`
169			`return 0, FormatError("uninitialized Huffman table")`
170			`}`
171			`for i, code := 0, 0; i < maxCodeLength; i++ {`
172			`err := d.ensureNBits(1)`
173			`if err != nil {`
174			`return 0, err`
175			`}`
176			`if d.b.a&d.b.m != 0 {`
177			`code \|= 1`
178			`}`
179			`d.b.n--`
180			`d.b.m >>= 1`
181			`if code <= h.maxCode[i] {`
182			`return h.val[h.valIndex[i]+code-h.minCode[i]], nil`
183			`}`
184			`code <<= 1`
185			`}`
186			`return 0, FormatError("bad Huffman code")`
187			`}`

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [image/] [jpeg/] [huffman.go] - Blame information for rev 747