bmp: decode 1, 2 and 4 bits-per-pixel palettes

Specification: https://www.digicamsoft.com/bmp/bmp.html

Fixes golang/go#29711
Fixes golang/go#58005

Change-Id: Ia6f7ac61af26c6379d9e610261070dfc9a9001b3
GitHub-Last-Rev: 12c6ab1cf21771e37bf76eb9a15d6b35a9aa8d3d
GitHub-Pull-Request: golang/image#22
Reviewed-on: https://go-review.googlesource.com/c/image/+/636975
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
Reviewed-by: Nigel Tao <nigeltao@golang.org>
Reviewed-by: Nigel Tao <nigeltao@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

 bmp/reader.go         |  39 +++++++++++++++++++++++----------------
 bmp/reader_test.go    |   3 +++
 testdata/bmp_1bpp.bmp | Bin 0 -> 938 bytes
 testdata/bmp_1bpp.png | Bin 0 -> 3946 bytes
 testdata/bmp_4bpp.bmp | Bin 0 -> 3624 bytes
 testdata/bmp_4bpp.png | Bin 0 -> 1134 bytes
 testdata/bmp_8bpp.bmp | Bin 0 -> 7128 bytes
 testdata/bmp_8bpp.png | Bin 0 -> 1134 bytes
 8 files changed, 26 insertions(+), 16 deletions(-)

diff --git a/bmp/reader.go b/bmp/reader.go
index 1939c11..fa9083d 100644
--- a/bmp/reader.go
+++ b/bmp/reader.go
@@ -26,28 +26,35 @@ func readUint32(b []byte) uint32 {
 	return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
 }
 
-// decodePaletted reads an 8 bit-per-pixel BMP image from r.
+// decodePaletted reads a 1, 2, 4 or 8 bit-per-pixel BMP image from r.
 // If topDown is false, the image rows will be read bottom-up.
-func decodePaletted(r io.Reader, c image.Config, topDown bool) (image.Image, error) {
+func decodePaletted(r io.Reader, c image.Config, topDown bool, bpp int) (image.Image, error) {
 	paletted := image.NewPaletted(image.Rect(0, 0, c.Width, c.Height), c.ColorModel.(color.Palette))
 	if c.Width == 0 || c.Height == 0 {
 		return paletted, nil
 	}
-	var tmp [4]byte
 	y0, y1, yDelta := c.Height-1, -1, -1
 	if topDown {
 		y0, y1, yDelta = 0, c.Height, +1
 	}
+
+	pixelsPerByte := 8 / bpp
+	// Pad up to ensure each row is 4-bytes aligned.
+	bytesPerRow := ((c.Width+pixelsPerByte-1)/pixelsPerByte + 3) &^ 3
+	b := make([]byte, bytesPerRow)
+
 	for y := y0; y != y1; y += yDelta {
 		p := paletted.Pix[y*paletted.Stride : y*paletted.Stride+c.Width]
-		if _, err := io.ReadFull(r, p); err != nil {
+		if _, err := io.ReadFull(r, b); err != nil {
 			return nil, err
 		}
-		// Each row is 4-byte aligned.
-		if c.Width%4 != 0 {
-			_, err := io.ReadFull(r, tmp[:4-c.Width%4])
-			if err != nil {
-				return nil, err
+		byteIndex, bitIndex, mask := 0, 8, byte((1<<bpp)-1)
+		for pixIndex := 0; pixIndex < c.Width; pixIndex++ {
+			bitIndex -= bpp
+			p[pixIndex] = (b[byteIndex]) >> bitIndex & mask
+			if bitIndex == 0 {
+				byteIndex++
+				bitIndex = 8
 			}
 		}
 	}
@@ -118,8 +125,8 @@ func Decode(r io.Reader) (image.Image, error) {
 		return nil, err
 	}
 	switch bpp {
-	case 8:
-		return decodePaletted(r, c, topDown)
+	case 1, 2, 4, 8:
+		return decodePaletted(r, c, topDown, bpp)
 	case 24:
 		return decodeRGB(r, c, topDown)
 	case 32:
@@ -190,12 +197,12 @@ func decodeConfig(r io.Reader) (config image.Config, bitsPerPixel int, topDown b
 		return image.Config{}, 0, false, false, ErrUnsupported
 	}
 	switch bpp {
-	case 8:
+	case 1, 2, 4, 8:
 		colorUsed := readUint32(b[46:50])
-		// If colorUsed is 0, it is set to the maximum number of colors for the given bpp, which is 2^bpp.
+
 		if colorUsed == 0 {
-			colorUsed = 256
-		} else if colorUsed > 256 {
+			colorUsed = 1 << bpp
+		} else if colorUsed > (1 << bpp) {
 			return image.Config{}, 0, false, false, ErrUnsupported
 		}
 
@@ -212,7 +219,7 @@ func decodeConfig(r io.Reader) (config image.Config, bitsPerPixel int, topDown b
 			// Every 4th byte is padding.
 			pcm[i] = color.RGBA{b[4*i+2], b[4*i+1], b[4*i+0], 0xFF}
 		}
-		return image.Config{ColorModel: pcm, Width: width, Height: height}, 8, topDown, false, nil
+		return image.Config{ColorModel: pcm, Width: width, Height: height}, int(bpp), topDown, false, nil
 	case 24:
 		if offset != fileHeaderLen+infoLen {
 			return image.Config{}, 0, false, false, ErrUnsupported
diff --git a/bmp/reader_test.go b/bmp/reader_test.go
index 003d64f..29a7f71 100644
--- a/bmp/reader_test.go
+++ b/bmp/reader_test.go
@@ -46,6 +46,9 @@ func TestDecode(t *testing.T) {
 		"video-001",
 		"yellow_rose-small",
 		"yellow_rose-small-v5",
+		"bmp_1bpp",
+		"bmp_4bpp",
+		"bmp_8bpp",
 	}
 
 	for _, tc := range testCases {
diff --git a/testdata/bmp_1bpp.bmp b/testdata/bmp_1bpp.bmp
new file mode 100644
index 0000000..e878830
Binary files /dev/null and b/testdata/bmp_1bpp.bmp differ
diff --git a/testdata/bmp_1bpp.png b/testdata/bmp_1bpp.png
new file mode 100644
index 0000000..8182428
Binary files /dev/null and b/testdata/bmp_1bpp.png differ
diff --git a/testdata/bmp_4bpp.bmp b/testdata/bmp_4bpp.bmp
new file mode 100644
index 0000000..a52a147
Binary files /dev/null and b/testdata/bmp_4bpp.bmp differ
diff --git a/testdata/bmp_4bpp.png b/testdata/bmp_4bpp.png
new file mode 100644
index 0000000..9461174
Binary files /dev/null and b/testdata/bmp_4bpp.png differ
diff --git a/testdata/bmp_8bpp.bmp b/testdata/bmp_8bpp.bmp
new file mode 100644
index 0000000..2d825ff
Binary files /dev/null and b/testdata/bmp_8bpp.bmp differ
diff --git a/testdata/bmp_8bpp.png b/testdata/bmp_8bpp.png
new file mode 100644
index 0000000..9461174
Binary files /dev/null and b/testdata/bmp_8bpp.png differ