examples/checksum/

# Adler-32, straight out of the sentence that defines it.
#
# Corpus material (CLAUDE.md §9). This module is the other half of `crc.hero`'s
# point: a 32-bit checksum with **no bitwise operator in it at all**. Adler-32
# is two running sums modulo a prime, so it needs `+` and `%` and nothing else,
# and its 32-bit result is an arrangement of two 16-bit halves rather than an
# overflowing register. Where CRC-32 shows what Heroes refuses (`u32`
# arithmetic), this shows what it does not have to refuse.
#
# THE DEFINITION, quoted from its source and fetched — RFC 1950
# § 2.2, the zlib format specification, where Adler-32 is normative:
#
#   Adler-32 is composed of two sums accumulated per byte: s1 is the sum of
#   all bytes, s2 is the sum of all s1 values. Both sums are done modulo
#   65521. s1 is initialized to 1, s2 to zero. The Adler-32 checksum is
#   stored as s2*65536 + s1 in most-significant-byte first (network) order.
#
# https://www.rfc-editor.org/rfc/rfc1950.txt
#
# THE ORACLE is Python 3's `zlib.adler32`, run — an implementation
# this one shares no line with: `0x00000001` for the empty string, `0x00620062`
# for `a`, `0x091e01de` for `123456789`, `0x08ab027a` for `foobar`,
# `0x11e60398` for `Wikipedia` and `0x0231016d` for the two bytes of `é`. All
# six are asserted below. The `Wikipedia` value is also the one this checksum
# is published with almost everywhere, which is why it is in the list.
#
# WHY 65521, and why the program says it rather than 65536: it is the largest
# prime below 2^16, and the primality is the whole reason the sum catches
# transpositions that a plain sum does not. The test at the bottom asserts it
# is prime, so the number is a fact in this program and not a magic constant.

# The modulus: the largest prime below 65536.
constant BASE: i64
    65521

# The two halves of an Adler-32, each of them a 16-bit value by construction
# because both are taken modulo `BASE`. Declared `u16` so the width is in the
# type rather than in a comment — `s2 * 65536 + s1` then says how they are put
# together, exactly as RFC 1950 writes it.
record Halves
    s1: u16
    s2: u16

# The two sums of `text`, in the order the RFC names them.
function halves(text: str) -> Halves
    s1: i64 @= 1
    s2: i64 @= 0
    i: i64 @= 0

    while i < text.len()
        byte: u8 = text[i]
        s1 @ (s1 + byte.to_i64().must()) % BASE
        s2 @ (s2 + s1) % BASE
        i @ i + 1

    return Halves(s1: s1.to_u16().must(), s2: s2.to_u16().must())

# The checksum itself: `s2 * 65536 + s1`, the RFC's own arrangement.
function adler32(text: str) -> u32
    two = halves(text)
    return (two.s2.to_i64().must() * 65536 + two.s1.to_i64().must()).to_u32().must()

# Whether `n` has no divisor but itself and one — used only by the test that
# asserts `BASE` is prime.
function is_prime(n: i64) -> bool
    if n < 2
        return false
    d: i64 @= 2

    while d * d <= n
        if n % d == 0
            return false
        d @ d + 1

    return true

test "six values from an implementation this one shares no line with"
    # Run against Python 3's `zlib.adler32`.
    assert adler32("") == 0x00000001
    assert adler32("a") == 0x00620062
    assert adler32("123456789") == 0x091e01de
    assert adler32("foobar") == 0x08ab027a
    assert adler32("Wikipedia") == 0x11e60398
    assert adler32("é") == 0x0231016d

test "the empty string is s1 = 1 and s2 = 0, which is the RFC's initialisation"
    # The one value the definition gives directly, asserted through the halves
    # rather than through the packed number, so a mistake in the packing and a
    # mistake in the initialisation cannot hide each other.
    empty = halves("")
    assert empty.s1 == 1
    assert empty.s2 == 0
    assert adler32("") == 1

test "s1 is the sum of the bytes, plus the one it started at"
    # `a` is 97, `b` is 98, `c` is 99, and a character literal is an integer
    # (spec § Types), so the sum can be written out rather than trusted.
    three = halves("abc")
    assert three.s1.to_i64().must() == 1 + 'a' + 'b' + 'c'

    # s2 accumulates s1 after each byte: (1+97) + (1+97+98) + (1+97+98+99).
    assert three.s2.to_i64().must() == 98 + 196 + 295

test "moving a byte changes the checksum, which a plain sum would not notice"
    # This is what the second sum BUYS, and it is the reason Adler-32 is not
    # just s1. The first assertion is the one a plain byte sum fails.
    assert halves("ab").s1 == halves("ba").s1
    assert adler32("ab") != adler32("ba")
    assert adler32("abcd") != adler32("dcba")

test "the modulus is the largest prime below sixty-five thousand five hundred and thirty-six"
    # `BASE` is a fact in this program rather than a number somebody copied.
    assert is_prime(BASE)
    assert BASE < 65536
    n: i64 @= BASE + 1

    while n < 65536
        assert !is_prime(n)
        n @ n + 1

test "both halves stay inside sixteen bits, whatever the message"
    # The claim `record Halves` makes in its types, made falsifiable: if either
    # sum could exceed 65535 the `to_u16()` would abort, and this walks a
    # message long enough to have wrapped both sums many times.
    long = repeat("the quick brown fox jumps over the lazy dog", 200)
    assert long.len() == 8600
    wide = halves(long)
    assert wide.s1.to_i64().must() < BASE
    assert wide.s2.to_i64().must() < BASE

    # And the packed value still agrees with the halves it was built from.
    assert adler32(long).to_i64().must() == wide.s2.to_i64().must() * 65536 + wide.s1.to_i64().must()

# Base64, both ways, against the vectors in the standard that defines it.
#
# Corpus material (CLAUDE.md §9). Where `crc.hero` and `adler.hero` turn bytes
# into a number, this turns bytes into text and back, which is the other half
# of what a checksum program does for a living: six bits at a time out of
# every three bytes, and the two padded shapes at the end that everybody gets
# wrong.
#
# THE ORACLE, fetched and quoted whole — RFC 4648 § 10, *Test
# Vectors*, the section the standard provides for exactly this purpose:
#
#   BASE64("") = ""
#   BASE64("f") = "Zg=="
#   BASE64("fo") = "Zm8="
#   BASE64("foo") = "Zm9v"
#   BASE64("foob") = "Zm9vYg=="
#   BASE64("fooba") = "Zm9vYmE="
#   BASE64("foobar") = "Zm9vYmFy"
#
# https://www.rfc-editor.org/rfc/rfc4648.txt
#
# All seven are asserted below in BOTH directions, which is more than the RFC
# writes down: the vectors are an encoding table, and reading them backwards is
# a second program.
#
# WHY DECODING STOPS AT BYTES, and this is the language rather than a choice.
# `decoded` returns `[u8]` and not `str`, because **Heroes has no way to build
# a character from a byte value**: the spec's conversions go the other way
# (`to_u8` takes a number and gives a number), a string literal is ASCII-only
# with six escapes and none of them numeric, and the runtime's byte-to-text
# door is `hero_str_from_bytes`, which takes a `ptr` — while `[u8]` in an
# `extern` position is `error[ffi_type]` today. So a decoder written in Heroes
# alone can hand back the bytes and nothing else, and the way to check them is
# `bytes_of` on the text they should be. This is a witness for M-core-packages'
# opening question (iii), the byte buffer, and it was found by writing the
# program rather than by reading the spec.

constant ALPHABET: str
    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"

constant PAD: str
    "="

constant ERR_LENGTH: str
    "base64_length"

constant ERR_CHARACTER: str
    "base64_character"

constant ERR_PADDING: str
    "base64_padding"

# The bytes of `text`, which is what a `str` already is (spec § Types) — this
# only changes the type, so that a caller can hand text to a byte-oriented
# function without the two ever being confused.
function bytes_of(text: str) -> [u8]
    out: [u8] @= []
    i: i64 @= 0

    while i < text.len()
        out @ out.push(text[i])
        i @ i + 1

    return out

# The character six bits stand for.
function letter(value: i64) -> str
    return ALPHABET.slice(from: value, to: value + 1)

# The six bits a character stands for, or a refusal naming it.
function value_of(written: str) -> i64?
    i: i64 @= 0

    while i < 64
        if ALPHABET.slice(from: i, to: i + 1) == written
            return ok(i)
        i @ i + 1

    return fail(code: ERR_CHARACTER, msg: "`" + written + "` is not one of base64's 64 characters")

# `text`, encoded. The general one takes bytes; this is the spelling the RFC's
# vectors are written in.
function encoded(text: str) -> str
    return encoded_bytes(bytes_of(text))

# Three bytes in, four characters out — and where there are not three, the
# missing sixth-bit groups become `=`, which is what makes the length of the
# output say how many bytes the last group held.
function encoded_bytes(data: [u8]) -> str
    out: [str] @= []
    i: i64 @= 0
    n = data.len()

    while i < n
        b0 = data[i].to_i64().must()
        b1: i64 @= 0
        b2: i64 @= 0
        held: i64 @= 1

        if i + 1 < n
            b1 @ data[i + 1].to_i64().must()
            held @ 2

        if i + 2 < n
            b2 @ data[i + 2].to_i64().must()
            held @ 3

        # `b0 << 16 | b1 << 8 | b2` is `((b0 << 16) | (b1 << 8)) | b2`: in
        # Heroes a shift binds tighter than `|` (spec § Operators), so the
        # parentheses a C programmer writes here are the ones `heroes fmt`
        # deletes.
        block = b0 << 16 | b1 << 8 | b2
        out @ out.push(letter(block >> 18 & 63))
        out @ out.push(letter(block >> 12 & 63))

        if held >= 2
            out @ out.push(letter(block >> 6 & 63))
        else
            out @ out.push(PAD)

        if held == 3
            out @ out.push(letter(block & 63))
        else
            out @ out.push(PAD)
        i @ i + 3

    return join(out, "")

# How many `=` close a four-character group, refusing the shapes that cannot
# occur: padding in the first two places, and a gap in the middle.
function padding_of(group: str) -> i64?
    third = group.slice(from: 2, to: 3)
    fourth = group.slice(from: 3, to: 4)

    if group.slice(from: 0, to: 1) == PAD || group.slice(from: 1, to: 2) == PAD
        return fail(
            code: ERR_PADDING,
            msg: "`=` cannot stand in the first two places of a group, and `" + group + "` has one there"
        )

    if third == PAD && fourth != PAD
        return fail(
            code: ERR_PADDING,
            msg: "`" + group + "` pads its third character and not its fourth, which no encoder writes"
        )

    if third == PAD
        return ok(2)

    if fourth == PAD
        return ok(1)

    return ok(0)

# `text`, decoded to the bytes it stands for — see the header for why this
# stops at bytes.
function decoded(text: str) -> [u8]?
    if text.len() % 4 != 0
        return fail(
            code: ERR_LENGTH,
            msg: "a base64 text is a multiple of four characters long, and this one is " + text.len().to_str()
        )
    out: [u8] @= []
    i: i64 @= 0

    while i < text.len()
        group = text.slice(from: i, to: i + 4)
        pad = padding_of(group)?

        if pad > 0 && i + 4 < text.len()
            return fail(code: ERR_PADDING, msg: "`" + group + "` is padded and is not the last group")
        v0 = value_of(group.slice(from: 0, to: 1))?
        v1 = value_of(group.slice(from: 1, to: 2))?
        v2: i64 @= 0
        v3: i64 @= 0

        if pad < 2
            v2 @ value_of(group.slice(from: 2, to: 3))?

        if pad < 1
            v3 @ value_of(group.slice(from: 3, to: 4))?
        block = v0 << 18 | v1 << 12 | v2 << 6 | v3
        out @ out.push((block >> 16 & 255).to_u8().must())

        if pad < 2
            out @ out.push((block >> 8 & 255).to_u8().must())

        if pad < 1
            out @ out.push((block & 255).to_u8().must())
        i @ i + 4

    return ok(out)

# The code a decode refused with, or a sentence saying it did not — so a test
# can assert WHICH refusal happened in one line.
function refusal_of(said: [u8]?) -> str
    return match said
        .ok _  => "nothing was refused"
        .err e => e.code

test "the seven vectors of RFC 4648, encoding"
    # § 10 Test Vectors, fetched.
    assert encoded("") == ""
    assert encoded("f") == "Zg=="
    assert encoded("fo") == "Zm8="
    assert encoded("foo") == "Zm9v"
    assert encoded("foob") == "Zm9vYg=="
    assert encoded("fooba") == "Zm9vYmE="
    assert encoded("foobar") == "Zm9vYmFy"

test "the same seven, read backwards, which the RFC does not write down"
    assert decoded("").must() == bytes_of("")
    assert decoded("Zg==").must() == bytes_of("f")
    assert decoded("Zm8=").must() == bytes_of("fo")
    assert decoded("Zm9v").must() == bytes_of("foo")
    assert decoded("Zm9vYg==").must() == bytes_of("foob")
    assert decoded("Zm9vYmE=").must() == bytes_of("fooba")
    assert decoded("Zm9vYmFy").must() == bytes_of("foobar")

test "every length from nothing to seventeen bytes survives the round trip"
    # The three padded shapes repeat with period three, so seventeen lengths
    # cover each of them five times and the empty case once.
    text = "the quick brown fox"
    n: i64 @= 0

    while n <= 17
        piece = text.slice(from: 0, to: n)
        assert decoded(encoded(piece)).must() == bytes_of(piece)
        n @ n + 1

test "the length of the output says how many bytes the last group held"
    # Four characters per three bytes, always, and the `=` count is 3 - n % 3
    # where it is not zero.
    assert encoded("f").len() == 4
    assert encoded("fo").len() == 4
    assert encoded("foo").len() == 4
    assert encoded("foob").len() == 8
    assert encoded("the quick brown fox").len() == 28

test "a byte above ASCII goes through untouched, because a str is bytes"
    # `é` is two bytes (195 and 169), so it is one padded group, and the
    # decoder gives both bytes back.
    assert "é".len() == 2
    assert encoded("é") == "w6k="
    assert decoded("w6k=").must() == bytes_of("é")
    assert decoded("w6k=").must().len() == 2

test "the five refusals, each asserted by the code that names it"
    # Named refusals rather than a bare `is_err()`, which is `examples/ini/`'s
    # discipline: a decoder that refuses everything for one reason is a
    # decoder nobody can debug, and a test that only asks `is_err()` cannot
    # tell the two apart either.
    assert refusal_of(decoded("Zm9")) == ERR_LENGTH
    assert refusal_of(decoded("Zm9$")) == ERR_CHARACTER
    assert refusal_of(decoded("=m9v")) == ERR_PADDING
    assert refusal_of(decoded("Zm=v")) == ERR_PADDING
    assert refusal_of(decoded("Zg==Zg==")) == ERR_PADDING

    # And what is NOT refused: the last group may be padded, and only it.
    assert refusal_of(decoded("Zm9vYg==")) == "nothing was refused"

test "the alphabet is the standard one, in the standard order"
    # RFC 4648 § 4's table, asserted at its four corners and its length, so a
    # transposed character cannot hide behind a vector that happens to pass.
    assert ALPHABET.len() == 64
    assert letter(0) == "A"
    assert letter(25) == "Z"
    assert letter(26) == "a"
    assert letter(51) == "z"
    assert letter(52) == "0"
    assert letter(61) == "9"
    assert letter(62) == "+"
    assert letter(63) == "/"

test "a character and its value are each other's inverse, all sixty-four"
    i: i64 @= 0

    while i < 64
        assert value_of(letter(i)).must() == i
        i @ i + 1

    assert value_of("=").is_err()
    assert value_of(" ").is_err()

# CRC-32, with the catalogue's parameters written down rather than folded into
# the code — and the catalogue's own check value asserted below.
#
# Corpus material (CLAUDE.md §9). What this module is here for is
# the one place where Heroes and a 32-bit checksum disagree: **the bitwise
# operators are `i64` only** (spec § Operators), so there is no 32-bit register
# to overflow. The register is an `i64` that never grows, because every step is
# a shift RIGHT and an exclusive-or with a 32-bit constant, and the result is
# handed back as a `u32` at the boundary. A program that reached for `u32`
# arithmetic inside the loop would not compile, and that is the language
# refusing the shape rather than the author choosing one.
#
# THE ORACLE, fetched from the CRC catalogue and quoted whole:
#
#   CRC-32/ISO-HDLC
#   width=32  poly=0x04c11db7  init=0xffffffff  refin=true  refout=true
#   xorout=0xffffffff  check=0xcbf43926  residue=0xdebb20e3
#   Alias: CRC-32, CRC-32/ADCCP, CRC-32/V-42, CRC-32/XZ, PKZIP
#
# https://reveng.sourceforge.io/crc-catalogue/17plus.htm
#
# and `check` is defined by that catalogue as *the contents of the register
# after initialising, reading the UTF-8 string "123456789" (as 8-bit
# characters), optionally reflecting, and applying the final XOR*. So
# `crc32("123456789") == 0xcbf43926` is not this program's opinion.
#
# A SECOND SOURCE, measured the same day: Python 3's `zlib.crc32` — an
# implementation nothing here shares a line with — gives `0xcbf43926` for
# `123456789`, `0x00000000` for the empty string, `0xe8b7be43` for `a` and
# `0x9ef61f95` for `foobar`. All four are asserted below.
#
# WHY THE POLYNOMIAL IS WRITTEN 0xedb88320 IN THE LOOP. The catalogue's
# `poly` is 0x04c11db7 read most-significant-bit first; `refin=true` says the
# message bits arrive least-significant first, and the standard way to obey
# that is to walk the register rightwards with the polynomial's bits reversed.
# 0xedb88320 IS 0x04c11db7 reversed, and the test below asserts exactly that
# rather than asking the reader to take it on trust.

# The catalogue's `poly`, as the catalogue writes it.
constant POLY: i64
    0x04c11db7

# The same polynomial, bit-reversed, which is the form a rightwards walk needs.
constant POLY_REFLECTED: i64
    0xedb88320

# The catalogue's `init` and `xorout`. They are the same value here, which is
# true of CRC-32 and not of every model, so both are named.
constant INIT: i64
    0xffffffff

constant XOROUT: i64
    0xffffffff

# The CRC-32 of `text`, byte by byte.
#
# `reg` is an `i64` because `>>` and `^` are `i64`-only, and it stays inside 32
# bits without a mask: it starts at 0xffffffff, every step shifts it right, and
# the only value ever xored in is 32 bits wide. The `.to_u32()` at the end is
# where the width becomes part of the type instead of a fact about the loop.
function crc32(text: str) -> u32
    reg: i64 @= INIT
    i: i64 @= 0

    while i < text.len()
        byte: u8 = text[i]
        reg @ reg ^ byte.to_i64().must()
        bit: i64 @= 0

        while bit < 8
            # `reg & 1 == 1` is `(reg & 1) == 1`: in Heroes `&` binds tighter
            # than a comparison, the other way round from C, which is
            # `examples/palette/`'s lesson and is why there are no parentheses
            # here — `heroes fmt` deletes them.
            if reg & 1 == 1
                reg @ reg >> 1 ^ POLY_REFLECTED
            else
                reg @ reg >> 1
            bit @ bit + 1

        i @ i + 1

    return (reg ^ XOROUT).to_u32().must()

# The bits of `value`, most significant first, reversed — used only by the test
# that checks the reflected polynomial against the catalogue's.
function reversed_bits(value: i64, width: i64) -> i64
    out: i64 @= 0
    i: i64 @= 0

    while i < width
        out @ out << 1 | value >> i & 1
        i @ i + 1

    return out

test "the catalogue's check value, which this program did not invent"
    # CRC-32/ISO-HDLC, check=0xcbf43926 over "123456789". Fetched.
    assert crc32("123456789") == 0xcbf43926

test "three more values from an implementation this one shares no line with"
    # Python 3 `zlib.crc32`, run.
    assert crc32("") == 0x00000000
    assert crc32("a") == 0xe8b7be43
    assert crc32("foobar") == 0x9ef61f95

test "the reflected polynomial is the catalogue's polynomial, reversed"
    # The one derived constant in this module, derived in a test instead of in
    # a comment. If somebody mistypes `POLY_REFLECTED`, this fails before the
    # check value does, and it says which of the two is wrong.
    assert reversed_bits(value: POLY, width: 32) == POLY_REFLECTED
    assert reversed_bits(value: POLY_REFLECTED, width: 32) == POLY

test "reversing bits twice is where it started"
    assert reversed_bits(value: 1, width: 32) == 0x80000000
    assert reversed_bits(value: 0x80000000, width: 32) == 1
    assert reversed_bits(value: 0, width: 32) == 0
    assert reversed_bits(value: 0xffffffff, width: 32) == 0xffffffff
    assert reversed_bits(value: reversed_bits(value: 0x12345678, width: 32), width: 32) == 0x12345678

test "the empty string is init xored with xorout, which is zero here"
    # Not a coincidence worth hiding: with init == xorout the empty message's
    # CRC is 0, and the assertion says so in the parameters rather than in hex.
    assert crc32("") == (INIT ^ XOROUT).to_u32().must()

test "one changed byte changes the checksum, and so does one moved byte"
    # What a checksum is FOR, asserted rather than assumed.
    assert crc32("123456789") != crc32("123456780")
    assert crc32("ab") != crc32("ba")
    assert crc32("a") != crc32("aa")

test "the loop walks bytes and not characters"
    # A `str` is measured in bytes (spec § Types), so `é` is two of them and
    # the checksum covers both. The value is `zlib.crc32` on those two bytes,
    # 195 and 169, run — and it is here because a loop over
    # `text.chars()` would give a different answer while looking just as
    # reasonable.
    assert "é".len() == 2
    assert crc32("é") == 0x0e048d3e

test "the register never leaves 32 bits, at every step of a real message"
    # The claim the module's header rests on, made falsifiable: if any step
    # grew past 32 bits the mask-free implementation would be wrong, and the
    # check value alone would not say where.
    reg: i64 @= INIT
    i: i64 @= 0
    text = "123456789"

    while i < text.len()
        reg @ reg ^ text[i].to_i64().must()
        bit: i64 @= 0

        while bit < 8
            if reg & 1 == 1
                reg @ reg >> 1 ^ POLY_REFLECTED
            else
                reg @ reg >> 1
            assert reg >= 0
            assert reg <= 0xffffffff
            bit @ bit + 1

        i @ i + 1

    assert (reg ^ XOROUT).to_u32().must() == 0xcbf43926