gno.land/p/moul/x/daily/rle/v0⧉

1// Package rle implements run-length encoding as a pure, reusable package: runs2// 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 — a6// 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 on8// 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 from12// a count on the way back; Encode rejects them rather than round-tripping wrong.13//14// A live demo of this package is at15// [r/moul/x/daily/rledemo](/r/moul/x/daily/rledemo/v0).16package rle1718import (19	"errors"20	"strconv"21	"strings"22)2324// MaxLen bounds input so encode/decode gas stays predictable.25const MaxLen = 40962627var (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 be31	// 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)3637// Encode collapses runs of repeated bytes into <count><char> pairs.38func Encode(s string) (string, error) {39	if len(s) > MaxLen {40		return "", ErrTooLong41	}42	for i := 0; i < len(s); i++ {43		if s[i] >= '0' && s[i] <= '9' {44			return "", ErrDigit45		}46	}47	if s == "" {48		return "", nil49	}50	var b strings.Builder51	run := 152	for i := 1; i <= len(s); i++ {53		if i < len(s) && s[i] == s[i-1] {54			run++55			continue56		}57		b.WriteString(strconv.Itoa(run))58		b.WriteByte(s[i-1])59		run = 160	}61	return b.String(), nil62}6364// Decode expands <count><char> pairs back into the original string.65func Decode(s string) (string, error) {66	if len(s) > MaxLen {67		return "", ErrTooLong68	}69	var b strings.Builder70	i := 071	for i < len(s) {72		j := i73		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 character77			return "", ErrMalformed78		}79		n, err := strconv.Atoi(s[i:j])80		if err != nil || n <= 0 {81			return "", ErrMalformed82		}83		if b.Len()+n > MaxLen {84			return "", ErrTooLong // a short input can decode to an enormous one85		}86		b.WriteString(strings.Repeat(string(s[j]), n))87		i = j + 188	}89	return b.String(), nil90}9192// Ratio returns len(encoded)/len(original) as a percentage, rounded down.93// Over 100 means the encoding made the data BIGGER, which is the honest94// outcome for input without runs.95func Ratio(original, encoded string) int {96	if len(original) == 0 {97		return 098	}99	return len(encoded) * 100 / len(original)100}101