Files

576 lines
18 KiB
Go
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
// Copyright 2025 The Wuffs Authors.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
//
// SPDX-License-Identifier: Apache-2.0 OR MIT
// ----------------
//go:generate go run gen.go
// Package lowleveljpeg provides a JPEG encoder that takes in-DCT-space
// coefficients instead of in-XY-space pixels.
//
// It can be useful for experimenting with or visualizing in-DCT-space
// transformations, such as quantization, extrapolation and progressive-like
// reduction. Or for learning about how the JPEG file format works. But most
// programmers should use the Go standard library's image/jpeg package instead.
package lowleveljpeg
// See "the spec", also known as "the JPEG specification" or "ITU/CCITT T.81":
// https://www.w3.org/Graphics/JPEG/itu-t81.pdf
import (
"errors"
"io"
)
var (
ErrBadAddNForColorType = errors.New("lowleveljpeg: bad AddN for ColorType")
ErrBadArgument = errors.New("lowleveljpeg: bad argument")
ErrInvalidBlockI16 = errors.New("lowleveljpeg: invalid BlockI16")
ErrNilReceiver = errors.New("lowleveljpeg: nil receiver")
ErrPreviouslyReturnedError = errors.New("lowleveljpeg: previously returned error")
ErrTooManyAddNCalls = errors.New("lowleveljpeg: too many AddN calls")
)
// ColorType is a JPEG image's color type.
type ColorType byte
const (
// ColorTypeInvalid, the zero value, is invalid.
ColorTypeInvalid = ColorType(0)
// ColorTypeGray means a single channel (Gray).
ColorTypeGray = ColorType(1)
// ColorTypeYCbCr444 means three channels (Luma, Chroma-blue, Chroma-red),
// using 4:4:4 Chroma subsampling.
ColorTypeYCbCr444 = ColorType(3)
// ColorTypeYCbCr420 means three channels (Luma, Chroma-blue, Chroma-red),
// using 4:2:0 Chroma subsampling.
//
// This is the most popular color type for colorful (not gray) JPEG images.
ColorTypeYCbCr420 = ColorType(6)
// As an implementation detail, the constants' numerical value is the
// number of blocks in a JPEG MCU (Mininum Coded Unit).
)
// MCUDimensions returns the width and height of a Mininum Coded Unit.
func (c ColorType) MCUDimensions() (width int, height int) {
switch c {
case ColorTypeGray, ColorTypeYCbCr444:
return 8, 8
case ColorTypeYCbCr420:
return 16, 16
}
return 0, 0
}
func (c ColorType) isValid() bool {
switch c {
case ColorTypeGray, ColorTypeYCbCr444, ColorTypeYCbCr420:
return true
}
return false
}
// EncoderOptions are optional arguments to Encoder.Reset. The zero value is
// valid and means to use the default configuration.
type EncoderOptions struct {
// QuantizationFactors are the BlockI16 quantization factors. A nil pointer
// is equivalent to using DefaultQuality.
QuantizationFactors *Array2QuantizationFactors
// There may be other fields added in the future.
}
// Encoder writes JPEG-formatted bytes to an io.Writer.
//
// Call Reset and then AddN multiple times (N depends on the ColorType). Each
// AddN call encodes a Minimum Coded Unit (an 8×8 or 16×16 group of pixels,
// depending on the ColorType). Add MCUs in left-to-right top-to-bottom order.
// The final AddN call also writes the JPEG footer.
//
// AddN takes ArrayNBlockI16 arguments, which are post-FDCT (when encoding) or
// pre-IDCT (when decoding) coefficients.
//
// To get ArrayNBlockI16 values from pixels, use ExtractYCbCrFrom on an
// image.Image (to get an array of BlockU8 values) and then FowardDCTFrom (to
// get an array of BlockI16 values). See Example_basic for an example.
//
// An Encoder makes no allocations, other than the Encoder struct itself and
// any allocations that the passed io.Writer makes.
//
// An Encoder can be re-used, by calling Reset.
type Encoder struct {
hasReturnedError bool
colorType ColorType
prevDC [3]int16
numAddsRemaining uint32
bitsV uint32
bitsN uint32
quants Array2QuantizationFactors
// The fields above occupy 148 bytes. Each Reset or AddN call, in the worst
// case, emits not much more than 2688 bytes. We round sizeof(Encoder) up
// to be 3072, which is 1.5 times a power of 2.
buf [3072 - 148]byte
}
// Reset makes an Encoder ready to use (ready to make AddN calls), for encoding
// a JPEG with the given colorType, width and height.
//
// colorType should be ColorTypeGray, ColorTypeYCbCr444 or ColorTypeYCbCr420.
//
// width and height should both be positive but no larger than 0xFFFF, since a
// JPEG image cannot represent anything larger.
//
// options may be nil, which means to use the default configuration.
func (e *Encoder) Reset(w io.Writer, colorType ColorType, width int, height int, options *EncoderOptions) error {
if e == nil {
return ErrNilReceiver
} else if (width <= 0) || (0xFFFF < width) || (height <= 0) || (0xFFFF < height) || !colorType.isValid() {
e.hasReturnedError = true
return ErrBadArgument
}
if (options == nil) || (options.QuantizationFactors == nil) {
e.quants.SetToStandardValues(DefaultQuality)
} else {
q := options.QuantizationFactors
if !q[0].IsValid() || !q[1].IsValid() {
e.hasReturnedError = true
return ErrBadArgument
}
e.quants = *q
}
e.hasReturnedError = false
e.colorType = colorType
e.prevDC[0] = 0
e.prevDC[1] = 0
e.prevDC[2] = 0
if colorType != ColorTypeYCbCr420 {
e.numAddsRemaining = uint32((width+7)/8) * uint32((height+7)/8)
} else {
e.numAddsRemaining = uint32((width+15)/16) * uint32((height+15)/16)
}
e.bitsV = 0
e.bitsN = 0
e.buf[0] = 0xFF // SOI marker.
e.buf[1] = 0xD8
bufIndex := 2
bufIndex = e.encodeDQT(bufIndex)
bufIndex = e.encodeSOF0(bufIndex, width, height)
bufIndex = e.encodeDHT(bufIndex)
bufIndex = e.encodeSOSHeader(bufIndex)
if _, err := w.Write(e.buf[:bufIndex]); err != nil {
e.hasReturnedError = true
return err
}
return nil
}
// Add1 adds an 8×8 group of pixels to a ColorTypeGray image.
func (e *Encoder) Add1(w io.Writer, b *Array1BlockI16) error {
if e == nil {
return ErrNilReceiver
} else if e.hasReturnedError {
return ErrPreviouslyReturnedError
} else if e.colorType != ColorTypeGray {
e.hasReturnedError = true
return ErrBadAddNForColorType
} else if b == nil {
e.hasReturnedError = true
return ErrBadArgument
}
return e.addN(w, b[:])
}
// Add3 adds an 8×8 group of pixels to a ColorTypeYCbCr444 image.
func (e *Encoder) Add3(w io.Writer, b *Array3BlockI16) error {
if e == nil {
return ErrNilReceiver
} else if e.hasReturnedError {
return ErrPreviouslyReturnedError
} else if e.colorType != ColorTypeYCbCr444 {
e.hasReturnedError = true
return ErrBadAddNForColorType
} else if b == nil {
e.hasReturnedError = true
return ErrBadArgument
}
return e.addN(w, b[:])
}
// Add6 adds a 16×16 group of pixels to a ColorTypeYCbCr420 image.
func (e *Encoder) Add6(w io.Writer, b *Array6BlockI16) error {
if e == nil {
return ErrNilReceiver
} else if e.hasReturnedError {
return ErrPreviouslyReturnedError
} else if e.colorType != ColorTypeYCbCr420 {
e.hasReturnedError = true
return ErrBadAddNForColorType
} else if b == nil {
e.hasReturnedError = true
return ErrBadArgument
}
return e.addN(w, b[:])
}
func (e *Encoder) addN(w io.Writer, blocks []BlockI16) error {
for i := range blocks {
if !blocks[i].IsValid() {
e.hasReturnedError = true
return ErrInvalidBlockI16
}
}
if e.numAddsRemaining <= 0 {
e.hasReturnedError = true
return ErrTooManyAddNCalls
}
e.numAddsRemaining--
// In terms of worst case number of bytes emitted, the up-to-six
// encodeBlock calls can emit 2688 bytes (6 * 448 bytes).
whichComponents := ""
switch ColorType(len(blocks)) {
case ColorTypeGray:
whichComponents = "\x00"
case ColorTypeYCbCr444:
whichComponents = "\x00\x01\x02"
case ColorTypeYCbCr420:
whichComponents = "\x00\x00\x00\x00\x01\x02"
}
bufIndex := 0
for i := range blocks {
bufIndex = e.encodeBlock(bufIndex, whichComponents[i], &blocks[i])
}
if e.numAddsRemaining == 0 {
bufIndex = e.emitBits(bufIndex, 0x7F, 7)
e.buf[bufIndex+0] = 0xFF // EOI marker.
e.buf[bufIndex+1] = 0xD9
bufIndex += 2
}
if _, err := w.Write(e.buf[:bufIndex]); err != nil {
e.hasReturnedError = true
return err
}
return nil
}
func (e *Encoder) encodeDQT(bufIndex int) int {
e.buf[bufIndex+0] = 0xFF
e.buf[bufIndex+1] = 0xDB
e.buf[bufIndex+2] = 0x00
if e.colorType == ColorTypeGray {
e.buf[bufIndex+3] = 0x43
} else {
e.buf[bufIndex+3] = 0x84
}
bufIndex += 4
for i := range e.quants {
e.buf[bufIndex+0] = uint8(i)
bufIndex += 1
q := &e.quants[i]
for z := 0; z < 64; z++ {
e.buf[bufIndex+z] = q[zigzag[z]]
}
bufIndex += 64
if e.colorType == ColorTypeGray {
break
}
}
return bufIndex
}
func (e *Encoder) encodeSOF0(bufIndex int, width int, height int) int {
numComponents := byte(1)
if e.colorType != ColorTypeGray {
numComponents = byte(3)
}
e.buf[bufIndex+0] = 0xFF
e.buf[bufIndex+1] = 0xC0
e.buf[bufIndex+2] = 0x00
e.buf[bufIndex+3] = 0x08 + (3 * numComponents) // Payload length.
e.buf[bufIndex+4] = 0x08 // 8-bit depth.
e.buf[bufIndex+5] = byte(height >> 8)
e.buf[bufIndex+6] = byte(height >> 0)
e.buf[bufIndex+7] = byte(width >> 8)
e.buf[bufIndex+8] = byte(width >> 0)
e.buf[bufIndex+9] = numComponents
if e.colorType == ColorTypeGray {
e.buf[bufIndex+10] = 0x01 // Component ID 1.
e.buf[bufIndex+11] = 0x11 // Subsampling.
e.buf[bufIndex+12] = 0x00 // Quant selector 0.
return bufIndex + 13
}
lumaComponentSubsampling := byte(0x11)
if e.colorType == ColorTypeYCbCr420 {
lumaComponentSubsampling = byte(0x22)
}
// 4:4:4 subsampling. Luma and Chroma select Quant tables 0 and 1.
e.buf[bufIndex+10] = 0x01 // Component ID 1.
e.buf[bufIndex+11] = lumaComponentSubsampling
e.buf[bufIndex+12] = 0x00 // Quant selector 0.
e.buf[bufIndex+13] = 0x02 // Component ID 2.
e.buf[bufIndex+14] = 0x11 // Subsampling.
e.buf[bufIndex+15] = 0x01 // Quant selector 1.
e.buf[bufIndex+16] = 0x03 // Component ID 3.
e.buf[bufIndex+17] = 0x11 // Subsampling.
e.buf[bufIndex+18] = 0x01 // Quant selector 1.
return bufIndex + 19
}
func (e *Encoder) encodeDHT(bufIndex int) int {
s := ""
if e.colorType == ColorTypeGray {
s = hardCodedDHTSegments[:len(hardCodedDHTSegments)/2]
} else {
s = hardCodedDHTSegments
}
n := copy(e.buf[bufIndex:], s)
return bufIndex + n
}
func (e *Encoder) encodeSOSHeader(bufIndex int) int {
s := ""
if e.colorType == ColorTypeGray {
s = "\xFF\xDA" + // SOS marker.
"\x00\x08" + // Payload length.
"\x01" + // Number of components.
"\x01\x00" + // Component ID 1, Huffman selectors 0 (DC) and 0 (AC).
"\x00\x3F\x00" // Ss=0, Se=63, Ah=0, Al=0.
} else {
s = "\xFF\xDA" + // SOS marker.
"\x00\x0C" + // Payload length.
"\x03" + // Number of components.
"\x01\x00" + // Component ID 1, Huffman selectors 0 (DC) and 0 (AC).
"\x02\x11" + // Component ID 2, Huffman selectors 1 (DC) and 1 (AC).
"\x03\x11" + // Component ID 3, Huffman selectors 1 (DC) and 1 (AC).
"\x00\x3F\x00" // Ss=0, Se=63, Ah=0, Al=0.
}
n := copy(e.buf[bufIndex:], s)
return bufIndex + n
}
// In terms of worst case number of bytes emitted, encodeBlock can emit 448
// bytes (64 * 7 bytes), since there are 64 elements and each element could
// emit 7 bytes.
func (e *Encoder) encodeBlock(bufIndex int, whichComponent byte, b *BlockI16) int {
whichHuffmanBase := 0
if whichComponent > 0 {
whichHuffmanBase = 2
}
dc := div(b[0], int16(e.quants[whichHuffmanBase>>1][0]))
deltaDC := dc - e.prevDC[whichComponent]
e.prevDC[whichComponent] = dc
bufIndex = e.emitHuffmanRun(bufIndex, whichHuffmanBase+0, 0, int32(deltaDC))
zeroesRunLength := uint32(0)
for z := 1; z < 64; z++ {
zz := zigzag[z]
ac := div(b[zz], int16(e.quants[whichHuffmanBase>>1][zz]))
if ac == 0 {
zeroesRunLength++
continue
}
for ; zeroesRunLength >= 16; zeroesRunLength -= 16 {
bufIndex = e.emitHuffman(bufIndex, whichHuffmanBase+1, 0xF0)
}
bufIndex = e.emitHuffmanRun(bufIndex, whichHuffmanBase+1, zeroesRunLength, int32(ac))
zeroesRunLength = 0
}
if zeroesRunLength > 0 {
bufIndex = e.emitHuffman(bufIndex, whichHuffmanBase+1, 0x00)
}
return bufIndex
}
// emitHuffmanRun emits (zeroesRunLength, value) as two bitstrings. The first
// bitstring combines zeroesRunLength (also called RRRR) and the "category"
// part of value (also called SSSS). The second bitstring holds the "adjusted
// diff" part of value.
//
// The breakdown from value (a signed integer) into category and adjusted diff
// is a little complicated. Category is an unsigned integer less than 12 and
// smaller category mean values closer to zero. Adjusted diff is an unsigned
// integer less than (1 << category).
//
// Value Category Adjusted Diff
// 0 0 0
// -1, +1 1 0, 1
// -3, -2, +2, +3 2 0, 1, 2, 3
// -7, -6, -5, -4, +4, +5, +6, +7 3 0, 1, 2, 3, 4, 5, 6, 7
// -15, -14, ..., -8, +8, ..., +14, +15 4 0, 1, ..., 7, 8, ..., 14, 15
// etc etc
// -2047, ..., -1024, +1024, ..., +2047 11 0, ..., 1023, 1024, ..., 2047
//
// Compare with the JPEG spec, Tables F.1 and F.2, for the distinction between
// "diff" and "adjusted diff".
//
// For example, if value is -5 then category is 3 and adjDiff is 2 (0b010).
//
// For example, if value is -13 then category is 4 and adjDiff is 2 (0b0010).
//
// For example, if value is +15 then category is 4 and adjDiff is 15 (0b1111).
//
// At the bit level, the combined number ((zeroesRunLength << 4) | category),
// also known as ((RRRR << 4) | SSSS) in the spec, is Huffman-encoded. After
// that comes the adjDiff's bits, a bitstring whose length equals category.
//
// For DC values, zeroesRunLength is always zero and what's passed to this
// method is the delta from the previous DC value.
//
// For AC values, zeroesRunLength ranges from 0 up to 15 (inclusive). Category
// 11 is unused. Category 0 is also unused for AC values (as zeroes are run-
// length encoded), other than ((RRRR << 4) | SSSS) values of 0x00 and 0xF0
// being special cases:
//
// - 0x00 means that all remaining AC coefficients are zero.
// - 0xF0 means that the next 16 AC coefficients are zero.
//
// Pre-condition: value is in the range [-2047, +2047]. BlockI16.IsValid checks
// for [-1024, +1023] for DC and [-1023, +1023] for AC values. For DC values,
// what's then passed to this method is the delta from the previous DC value.
//
// In terms of worst case number of bytes emitted, emitHuffmanRun can emit 54
// bits, which rounds up to 7 bytes. To calculate that: category can range up
// to 11, so that emitHuffman + emitBits can emit 16 + 11 = 27 bits. Doubling
// that, because of 0xFF 0x00 byte stuffing, produces a worst case of 54.
func (e *Encoder) emitHuffmanRun(bufIndex int, whichHuffman int, zeroesRunLength uint32, value int32) int {
absValue, adjDiffBeforeMasking := uint32(value), uint32(value)
if value < 0 {
absValue, adjDiffBeforeMasking = uint32(-value), uint32(value-1)
}
category := uint32(0)
if absValue < 0x100 {
category = uint32(bitCount[absValue])
} else {
category = uint32(bitCount[absValue>>8]) + 8
}
combined := (zeroesRunLength << 4) | category
bufIndex = e.emitHuffman(bufIndex, whichHuffman, uint8(combined))
// At this point, we could say
//
// adjDiff := adjDiffBeforeMasking & ((1 << category) - 1)
//
// but it's equivalent to pass adjDiffBeforeMasking (instead of adjDiff) to
// emitBits, which does "v &= (1 << n) - 1" early in its function body.
bufIndex = e.emitBits(bufIndex, adjDiffBeforeMasking, category)
return bufIndex
}
// emitHuffman emits the Huffman-coded bits for value.
func (e *Encoder) emitHuffman(bufIndex int, whichHuffman int, value uint8) int {
x := huffmanBitWriters[whichHuffman][value]
return e.emitBits(bufIndex, x&0xFFFF, x>>16)
}
// emitBits emits the low n bits of v.
func (e *Encoder) emitBits(bufIndex int, v uint32, n uint32) int {
if n <= 0 {
return bufIndex
}
v &= (1 << n) - 1
n += e.bitsN
v <<= 32 - n
v |= e.bitsV
for ; n >= 8; n -= 8 {
vByte := byte(v >> 24)
e.buf[bufIndex] = vByte
bufIndex++
if vByte == 0xFF {
e.buf[bufIndex] = 0x00
bufIndex++
}
v <<= 8
}
e.bitsV = v
e.bitsN = n
return bufIndex
}
// div returns a/b rounded to the nearest integer, instead of rounded to zero.
//
// Pre-condition: b > 0.
func div(a, b int16) int16 {
if a >= 0 {
return (a + (b >> 1)) / b
}
return -((-a + (b >> 1)) / b)
}
// zigzag represents JPEG's zig-zag order for visiting coefficients. If b is a
// BlockI16 then b[zigzag[1]], b[zigzag[2]], b[zigzag[3]], ..., b[zigzag[63]]
// are its AC coefficients ordered from lowest to highest frequency, roughly
// speaking. b[0], which is also b[zigzag[0]], is the DC coefficient.
//
// https://en.wikipedia.org/wiki/File:JPEG_ZigZag.svg
var zigzag = [64]uint8{
0o00, 0o01, 0o10, 0o20, 0o11, 0o02, 0o03, 0o12, // 0, 1, 8, 16, 9, 2, 3, 10,
0o21, 0o30, 0o40, 0o31, 0o22, 0o13, 0o04, 0o05, // 17, 24, 32, 25, 18, 11, 4, 5,
0o14, 0o23, 0o32, 0o41, 0o50, 0o60, 0o51, 0o42, // 12, 19, 26, 33, 40, 48, 41, 34,
0o33, 0o24, 0o15, 0o06, 0o07, 0o16, 0o25, 0o34, // 27, 20, 13, 6, 7, 14, 21, 28,
0o43, 0o52, 0o61, 0o70, 0o71, 0o62, 0o53, 0o44, // 35, 42, 49, 56, 57, 50, 43, 36,
0o35, 0o26, 0o17, 0o27, 0o36, 0o45, 0o54, 0o63, // 29, 22, 15, 23, 30, 37, 44, 51,
0o72, 0o73, 0o64, 0o55, 0o46, 0o37, 0o47, 0o56, // 58, 59, 52, 45, 38, 31, 39, 46,
0o65, 0o74, 0o75, 0o66, 0o57, 0o67, 0o76, 0o77, // 53, 60, 61, 54, 47, 55, 62, 63,
}
// bitCount[i] is the smallest n such that i < (1 << n).
var bitCount = [256]byte{
0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
}