8
\$\begingroup\$

I'm not sure if this kind of golf is allowed, but here it is.

Your objective is to create an image containing one pixel of every possible RGB color. The image with the smallest file size wins.

Rules:

  • The image must be a PNG.
  • The image must contain exactly one of every possible RGB color.
  • Acceptable image dimensions are:
1x16777216
2x8388608
4x4194304
8x2097152
16x1048576
32x524288
64x262144
128x131072
256x65536
512x32768
1024x16384
2048x8192
4096x4096
8192x2048
16384x1024
32768x512
65536x256
131072x128
262144x64
524288x32
1048576x16
2097152x8
4194304x4
8388608x2
16777216x1

Example Image Example image

\$\endgroup\$
17
  • 4
    \$\begingroup\$ I think this has already been done, albeit as a popularity contest. \$\endgroup\$
    – user
    Jan 12 at 14:35
  • 6
    \$\begingroup\$ @cairdcoinheringaahing I think the sentence "the image with the smallest file size wins" in a challenge named "Smallest image containing one of every RGB color" very strongly suggests that the image with the smallest file size wins. (note: I'm not OP) \$\endgroup\$ Jan 12 at 15:12
  • 4
    \$\begingroup\$ Also, as no one has said it yet, welcome to the site! In the future, we recommend using the Sandbox to get feedback on challenge ideas before posting to main \$\endgroup\$ Jan 12 at 15:21
  • 2
    \$\begingroup\$ Why is this being close voted? \$\endgroup\$ Jan 12 at 16:27
  • 7
    \$\begingroup\$ The challenge to me seems pretty clearly specified - craft a PNG with one of every color with the smallest file size by any means necessary (by hand, by code, etc.) \$\endgroup\$
    – Sisyphus
    Jan 13 at 1:56
7
\$\begingroup\$

49683 49280 49131 bytes

image

Generated by this Python code. I designed the PNG scanlines by hand to be encoded using repetitions of short sequences that compress well. I’ve now written enough of a custom DEFLATE encoder to let me decide where to split the compressed blocks (saving 149 bytes compared to zlib).

import itertools
import struct
import zlib


def lsb(b, n):
    assert 0 <= n < 1 << b
    return f"{n:0{b}b}"[::-1] if b else ""


def huffman(lengths, letter):
    code = sum(
        1 << lengths[letter] - length
        for other_letter, length in lengths.items()
        if (length, other_letter) < (lengths[letter], letter)
    )
    return f"{code:0{lengths[letter]}b}"


def literal(letter):
    assert 0 <= letter < 256
    return huffman(literals, letter)


def end():
    return huffman(literals, 256)


def match(length, distance):
    assert 3 <= length <= 258
    assert 1 <= distance <= 32768

    if length == 258:
        bits = huffman(literals, 285)
    else:
        i = max(0, (length - 3).bit_length() - 3)
        bits = huffman(literals, 4 * i + 257 + (length - 3 >> i)) + lsb(
            i, length - 3 & ~(~0 << i)
        )

    j = max(0, (distance - 1).bit_length() - 2)
    bits += huffman(distances, 2 * j + (distance - 1 >> j)) + lsb(
        j, distance - 1 & ~(~0 << j)
    )

    return bits


code_length_order = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]


def encode_lengths():
    hlit = max(literals) + 1 - 257
    hdist = max(distances) + 1 - 1
    hclen = max(map(code_length_order.index, code_lengths)) + 1 - 4
    bits = lsb(5, hlit) + lsb(5, hdist) + lsb(4, hclen)
    for i in code_length_order[: hclen + 4]:
        bits += lsb(3, code_lengths.get(i, 0))
    for length, group in itertools.groupby(
        [literals.get(i, 0) for i in range(hlit + 257)]
        + [distances.get(i, 0) for i in range(hdist + 1)],
        lambda length: length,
    ):
        n = len(list(group))
        while length == 0 and 18 in code_lengths and n >= 11:
            bits += huffman(code_lengths, 18) + lsb(7, min(n - 11, 127))
            n -= min(n - 11, 127) + 11
        while length == 0 and 17 in code_lengths and n >= 3:
            bits += huffman(code_lengths, 17) + lsb(3, min(n - 3, 7))
            n -= min(n - 3, 7) + 3
        # not implemented: 16 (copy previous code)
        bits += huffman(code_lengths, length) * n
    return bits


png_header = struct.pack(
    "!IIBBBBB",
    2 ** 16,  # width
    2 ** 8,  # height
    8,  # bit depth
    2,  # color type
    0,  # compression method
    0,  # filter method
    0,  # interlace method
)

zlib_header = struct.pack(
    "!BB",
    8 | 7 << 4,  # compression method, compression info
    26 | 0 << 5 | 3 << 6,  # check bits, preset dictionary, compression level
)

literals = {1: 2, 2: 4, 256: 4, 268: 4, 284: 4, 285: 1}
distances = {2: 1, 18: 1}
code_lengths = {0: 3, 1: 2, 2: 3, 4: 2, 18: 2}
bits = "0"  # start non-final block
bits += lsb(2, 2)  # compressed with dynamic Huffman codes
bits += encode_lengths()
bits += literal(1) + literal(1) + literal(1) + literal(2) + literal(1) + literal(2)
bits += 2 * match(258, 3)
bits += match(248, 3)
bits += 5 * (
    match(258, 768) + match(258, 3) + 42 * (match(258, 768) + 2 * match(258, 3))
)
bits += match(258, 768) + match(258, 3) + 39 * (match(258, 768) + 2 * match(258, 3))
bits += match(17, 3)
bits += end()

literals = {1: 3, 256: 3, 264: 3, 279: 3, 285: 1}
distances = {0: 1, 2: 1}
code_lengths = {0: 3, 1: 2, 3: 2, 17: 3, 18: 2}
bits += "1"  # start final block
bits += lsb(2, 2)  # compressed with dynamic Huffman codes
bits += encode_lengths()
bits += 96780 * match(258, 1)
bits += match(105, 1)
bits += literal(1) + literal(1)
bits += 762 * match(258, 3)
bits += match(10, 3)
bits += 96780 * match(258, 1)
bits += match(102, 1)
bits += end()

bits += -len(bits) % 8 * "0"
compressed = int(bits[::-1], 2).to_bytes((len(bits) + 7) // 8, "little")

decompressed = zlib.decompress(compressed, wbits=-15)
assert decompressed == bytes(
    [1, *(2 ** 8) * [1, 1, 2, *(2 ** 8 - 1) * [1, 2, 2]]]
    + (2 ** 7 - 1) * [2, *2 ** 16 * [2, 2, 2]]
    + [2, *2 ** 16 * [2, 1, 1]]
    + (2 ** 7 - 1) * [2, *2 ** 16 * [2, 2, 2]]
)

zlib_checksum = struct.pack("!I", zlib.adler32(decompressed))
png_data = zlib_header + compressed + zlib_checksum

png = b"\x89PNG\r\n\x1a\n"
for type, data in [(b"IHDR", png_header), (b"IDAT", png_data), (b"IEND", b"")]:
    crc = 0xFFFFFFFF
    for byte in type + data:
        crc ^= byte
        for bit in range(8):
            crc = 0xEDB88320 * (crc & 1) ^ crc >> 1
    crc ^= 0xFFFFFFFF
    png += struct.pack("!I4s", len(data), type) + data + struct.pack("!I", crc)

print(len(png))
with open("rgb.png", "wb") as f:
    f.write(png)

Try it online!

(Note: many PNG readers accept an image missing the IEND chunk, but it is required by the PNG specification so I have included it.)

\$\endgroup\$
2
\$\begingroup\$

256x65536, 49909 bytes

enter image description here

In my experience Google Chrome is the best tool to view this image.

The red channel starts at 255 in the first row and decreases by 1 each row.
The green channel slowly decreases from 255 to 0 in every row and the blue channel repeatly decreases from 255 to 0.

Generated by the following code in Python 3 with numpy and imageio:

import os

import imageio
import numpy as np

FILENAME = 'out.png'
DTYPE = np.uint8

values = np.arange(255, -1, -1, dtype=DTYPE)
image = np.empty((256, 256**2, 3), dtype=DTYPE)

image[..., 0] = values[:, np.newaxis]  # r
image[..., 1] = np.repeat(values, 256) # g
image[..., 2] = np.tile(values, 256)   # b

# Verify that all colors are present (slow)
# assert len(np.unique(image.reshape(256**3, 3), axis=0)) == 256 ** 3

imageio.imwrite(FILENAME, image)
os.system('wc ' + FILENAME)

I tried to reduce the file size with zopflipng, but even after 50 minutes of running it provided no improvement.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.