rle.gno

  1// Package rle implements run-length encoding as a pure, reusable package: runs
  2// of a repeated byte collapse to a count and the byte.
  3//
  4// The encoding is `<count><char>` with counts in decimal, e.g. "aaabbc" →
  5// "3a2b1c". Every run is emitted with its count, including runs of one — a
  6// uniform grammar is cheaper to decode and impossible to get subtly wrong,
  7// at the cost of expanding data that has no runs at all. RLE is a *win only on
  8// runny data*; Encode can legitimately produce output longer than its input,
  9// and the demo shows exactly that case rather than hiding it.
 10//
 11// Digits cannot appear in the input, since they would be indistinguishable from
 12// a count on the way back; Encode rejects them rather than round-tripping wrong.
 13//
 14// A live demo of this package is at
 15// [r/moul/x/daily/rledemo](/r/moul/x/daily/rledemo/v0).
 16package rle
 17
 18import (
 19	"errors"
 20	"strconv"
 21	"strings"
 22)
 23
 24// MaxLen bounds input so encode/decode gas stays predictable.
 25const MaxLen = 4096
 26
 27var (
 28	// ErrTooLong is returned when input exceeds MaxLen.
 29	ErrTooLong = errors.New("rle: input too long")
 30	// ErrDigit is returned when input contains a digit, which would be
 31	// ambiguous with a run count.
 32	ErrDigit = errors.New("rle: input must not contain digits")
 33	// ErrMalformed is returned when decoding input that is not <count><char>.
 34	ErrMalformed = errors.New("rle: malformed input")
 35)
 36
 37// Encode collapses runs of repeated bytes into <count><char> pairs.
 38func Encode(s string) (string, error) {
 39	if len(s) > MaxLen {
 40		return "", ErrTooLong
 41	}
 42	for i := 0; i < len(s); i++ {
 43		if s[i] >= '0' && s[i] <= '9' {
 44			return "", ErrDigit
 45		}
 46	}
 47	if s == "" {
 48		return "", nil
 49	}
 50	var b strings.Builder
 51	run := 1
 52	for i := 1; i <= len(s); i++ {
 53		if i < len(s) && s[i] == s[i-1] {
 54			run++
 55			continue
 56		}
 57		b.WriteString(strconv.Itoa(run))
 58		b.WriteByte(s[i-1])
 59		run = 1
 60	}
 61	return b.String(), nil
 62}
 63
 64// Decode expands <count><char> pairs back into the original string.
 65func Decode(s string) (string, error) {
 66	if len(s) > MaxLen {
 67		return "", ErrTooLong
 68	}
 69	var b strings.Builder
 70	i := 0
 71	for i < len(s) {
 72		j := i
 73		for j < len(s) && s[j] >= '0' && s[j] <= '9' {
 74			j++
 75		}
 76		if j == i || j == len(s) { // no count, or a count with no character
 77			return "", ErrMalformed
 78		}
 79		n, err := strconv.Atoi(s[i:j])
 80		if err != nil || n <= 0 {
 81			return "", ErrMalformed
 82		}
 83		if b.Len()+n > MaxLen {
 84			return "", ErrTooLong // a short input can decode to an enormous one
 85		}
 86		b.WriteString(strings.Repeat(string(s[j]), n))
 87		i = j + 1
 88	}
 89	return b.String(), nil
 90}
 91
 92// Ratio returns len(encoded)/len(original) as a percentage, rounded down.
 93// Over 100 means the encoding made the data BIGGER, which is the honest
 94// outcome for input without runs.
 95func Ratio(original, encoded string) int {
 96	if len(original) == 0 {
 97		return 0
 98	}
 99	return len(encoded) * 100 / len(original)
100}