+// Adapted from Eric Bodden's "Arithmetic Coding Revealed",
+// http://www.sable.mcgill.ca/publications/techreports/2007-5/bodden-07-arithmetic-TR.pdf
+package ac
+
+import "io"
+
+type Codec interface {
+ SetFileOutput(f io.Writer)
+ Encode(low_count uint32, high_count uint32, total uint32)
+ EncodeFinish()
+
+ SetFileInput(f io.Reader)
+ DecodeStart()
+ DecodeTarget(total uint32) uint32
+ Decode(low_count uint32, high_count uint32)
+}
+
+const (
+ g_FirstQuarter = 0x20000000
+ g_ThirdQuarter = 0x60000000
+ g_Half = 0x40000000
+)
+
+type codecState struct {
+ // Two different file variables, depending on whether we're reading or
+ // writing
+ readFile io.Reader
+ writeFile io.Writer
+ // Bit I/O buffer
+ bitCount uint8
+ bitBuffer byte
+ // encode/decode state
+ low, high, step, scale uint32
+ // decoder buffer
+ buffer uint32
+}
+
+func NewCodec() *codecState {
+ return &codecState{
+ nil,
+ nil,
+ 0,
+ 0,
+ 0, 0x7FFFFFFF, 0, 0, // mHigh uses 31-bits to prevent overflow
+ 0,
+ }
+}
+
+func (self *codecState) SetFileInput(f io.Reader) {
+ self.readFile = f.(io.Reader)
+}
+
+func (self *codecState) SetFileOutput(f io.Writer) {
+ self.writeFile = f.(io.Writer)
+}
+
+func (self *codecState) setBit(bit uint8) {
+ // Shift one bit onto the buffer (bit therefore should only be 0 or 1)
+ self.bitBuffer = (self.bitBuffer << 1) | bit
+ self.bitCount++
+
+ if self.bitCount == 8 {
+ // Buffer full -- write to output
+ _, err := self.writeFile.Write([]byte{self.bitBuffer})
+ if err != nil {
+ panic("Failed to write during setBit()")
+ }
+ self.bitCount = 0
+ }
+}
+
+func (self *codecState) setBitFlush() {
+ // Fill remainder of the bit buffer with zeroes
+ for self.bitCount != 0 {
+ self.setBit(0)
+ }
+}
+
+func (self *codecState) getBit() uint8 {
+ if (self.bitCount == 0) {
+ // Buffer is empty -- read from input
+ var b [1]byte
+ n, err := self.readFile.Read(b[:])
+ if n == 0 && err == io.EOF {
+ self.bitBuffer = 0
+ } else if n == 1 {
+ self.bitBuffer = b[0]
+ }
+ self.bitCount = 8
+ }
+
+ // Shift one bit out of the buffer
+ bit := uint8(self.bitBuffer >> 7)
+ self.bitBuffer <<= 1
+ self.bitCount--
+
+ return bit
+}
+
+func (self *codecState) Encode(low_count uint32, high_count uint32, total uint32) {
+ // Partition number space into single steps
+ self.step = (self.high - self.low + 1) / total
+ // Update upper bound
+ self.high = self.low + self.step * high_count - 1
+ // Update lower bound
+ self.low = self.low + self.step * low_count
+
+ // Apply e1/e2 scaling
+ for self.high < g_Half || self.low >= g_Half {
+ if self.high < g_Half {
+ self.setBit(0)
+ self.low = self.low * 2
+ self.high = self.high * 2 + 1
+
+ // Unwind e3 scaling
+ for ; self.scale > 0; self.scale-- {
+ self.setBit(1)
+ }
+ } else if self.low >= g_Half {
+ self.setBit(1)
+ self.low = 2 * (self.low - g_Half)
+ self.high = 2 * (self.high - g_Half)
+
+ // Unwind e3 scaling
+ for ; self.scale > 0; self.scale-- {
+ self.setBit(0)
+ }
+ }
+ }
+
+ // Apply e3 scaling and store scale for later e1/e2 scaling
+ for g_FirstQuarter <= self.low && self.high < g_ThirdQuarter {
+ self.scale++
+ self.low = 2 * (self.low - g_FirstQuarter)
+ self.high = 2 * (self.high - g_FirstQuarter) + 1
+ }
+}
+
+func (self *codecState) EncodeFinish() {
+ // There are two possibilities of how low and high can be distributed,
+ // which means that two bits are enough to distinguish them.
+ if self.low < g_FirstQuarter {
+ self.setBit(0)
+ for i := uint32(0); i < self.scale + 1; i++ {
+ self.setBit(1)
+ }
+ } else {
+ self.setBit(1)
+ }
+ self.setBitFlush()
+}
+
+func (self *codecState) DecodeStart() {
+ // Fill buffer with input
+ for i := 0; i < 31; i++ {
+ self.buffer = (self.buffer << 1) | uint32(self.getBit())
+ }
+}
+
+func (self *codecState) DecodeTarget(total uint32) uint32 {
+ self.step = (self.high - self.low + 1) / total
+
+ return (self.buffer - self.low) / self.step
+}
+
+func (self *codecState) Decode(low_count uint32, high_count uint32) {
+ // Update upper bound
+ self.high = self.low + self.step * high_count - 1
+
+ // Update lower bound
+ self.low = self.low + self.step * low_count
+
+ // Apply e1/e2 scaling
+ for self.high < g_Half || self.low >= g_Half {
+ if self.high < g_Half {
+ self.low = self.low * 2
+ self.high = self.high * 2 + 1
+ self.buffer = 2 * self.buffer + uint32(self.getBit())
+ } else if self.low >= g_Half {
+ self.low = 2 * (self.low - g_Half)
+ self.high = 2 * (self.high - g_Half)
+ self.buffer = 2 * (self.buffer - g_Half) + uint32(self.getBit())
+ }
+ self.scale = 0
+ }
+
+ // Apply e3 scaling
+ for g_FirstQuarter <= self.low && self.high < g_ThirdQuarter {
+ self.scale++
+ self.low = 2 * (self.low - g_FirstQuarter)
+ self.high = 2 * (self.high - g_FirstQuarter) + 1
+ self.buffer = 2 * (self.buffer - g_FirstQuarter) + uint32(self.getBit())
+ }
+}
+package ac
+
+import (
+ "io"
+)
+
+type CodecManager interface {
+ AddModel(context ModelContext, model Model)
+ Encode(context ModelContext, symbol uint32)
+ Decode(context ModelContext) uint32
+ Finish()
+}
+
+type ModelContext int
+
+type codecManager struct {
+ ac Codec
+ source io.Reader
+ target io.Writer
+ encoding bool
+ models map[ModelContext]Model
+}
+
+func NewEncoder(target io.Writer) (CodecManager, error) {
+ e := &codecManager{
+ NewCodec(),
+ nil,
+ target,
+ true,
+ make(map[ModelContext]Model),
+ }
+
+ e.ac.SetFileOutput(target)
+
+ return e, nil
+}
+
+func NewDecoder(source io.Reader) (CodecManager, error) {
+ e := &codecManager{
+ NewCodec(),
+ source,
+ nil,
+ false,
+ make(map[ModelContext]Model),
+ }
+
+ e.ac.SetFileInput(source)
+ e.ac.DecodeStart()
+
+ return e, nil
+}
+
+func (self *codecManager) AddModel(context ModelContext, model Model) {
+ self.models[context] = model
+}
+
+func (self *codecManager) Encode(context ModelContext, symbol uint32) {
+ self.models[context].Encode(self.ac, symbol)
+}
+
+func (self *codecManager) Finish() {
+ if self.encoding {
+ self.ac.EncodeFinish()
+ }
+}
+
+func (self *codecManager) Decode(context ModelContext) uint32 {
+ return self.models[context].Decode(self.ac)
+}
+package ac
+
+type Model interface {
+ Encode(ac Codec, symbol uint32)
+ Decode(ac Codec) uint32
+}
+package ac
+
+type modelOrder0 struct {
+ cumulativeCount []uint32
+ total uint32
+ n_symbols uint
+}
+
+func NewModelOrder0PreBias(n_sym uint, biases []uint32) Model {
+ if len(biases) != int(n_sym) {
+ panic("Wrong number of biases in order 0 model")
+ }
+ total := uint32(0)
+ for _, n := range(biases) {
+ total += n
+ }
+ obj := modelOrder0{
+ biases,
+ total,
+ n_sym,
+ }
+ return &obj
+}
+
+func NewModelOrder0(n_sym uint) Model {
+ biases := make([]uint32, n_sym)
+ for i := uint(0); i < n_sym; i++ {
+ biases[i] = 1
+ }
+ return NewModelOrder0PreBias(n_sym, biases)
+}
+
+func (self *modelOrder0) Encode(ac Codec, symbol uint32) {
+ // Accumulate frequencies
+ low_count := uint32(0)
+ var j uint32
+ for j = 0; j < symbol; j++ {
+ low_count += self.cumulativeCount[j]
+ }
+
+ ac.Encode(low_count, low_count + self.cumulativeCount[j], self.total)
+
+ self.cumulativeCount[symbol]++
+ self.total++
+}
+
+func (self *modelOrder0) Decode(ac Codec) uint32 {
+ var symbol uint32
+
+ var value uint32
+
+ value = ac.DecodeTarget(self.total)
+
+ low_count := uint32(0)
+
+ for symbol = 0; low_count + self.cumulativeCount[symbol] <= value; symbol++ {
+ low_count += self.cumulativeCount[symbol]
+ }
+
+ ac.Decode(low_count, low_count + self.cumulativeCount[symbol])
+
+ self.cumulativeCount[symbol]++
+ self.total++
+
+ return symbol
+}
+package main
+
+import (
+ "errors"
+ "fmt"
+ "image"
+ "image/color"
+ "io"
+ "math"
+ "reflect"
+ "log"
+ "os"
+ "sort"
+
+ _ "image/png"
+
+ "bytex64.net/code/bitsmash/packet"
+ "bytex64.net/code/bitsmash/ac"
+)
+
+type scanFunc func(pixels []uint8) packet.Packet
+
+var scanFuncs []scanFunc = []scanFunc {
+ packet.ScanRLE,
+ packet.ScanBinaryPattern,
+ packet.ScanDirect,
+}
+
+var sizes []int = []int{
+ 8,
+ 16,
+ 24,
+ 32,
+ 48,
+ 64,
+ 96,
+ 128,
+}
+
+func validSize(s int) bool {
+ for _, n := range(sizes) {
+ if n == s {
+ return true
+ }
+ }
+ return false
+}
+
+func sizeIndex(s int) int {
+ for i, n := range(sizes) {
+ if n == s {
+ return i
+ }
+ }
+ return -1
+}
+
+type BitSmash struct {
+ size int
+ palette int
+ transparent bool
+ n_colors uint
+ packetList []packet.Packet
+}
+
+func loadImage(filename string) image.PalettedImage {
+ reader, err := os.Open(filename)
+ if err != nil {
+ log.Fatal(err)
+ }
+ defer reader.Close()
+
+ img, _, err := image.Decode(reader)
+ if err != nil {
+ log.Fatal(err)
+ }
+
+ size := img.Bounds().Size()
+ if !validSize(size.X) {
+ log.Fatal(fmt.Sprintf("Image dimensions must be one of %v", sizes))
+ }
+
+ cm := img.ColorModel()
+ if reflect.TypeOf(cm).String() != "color.Palette" {
+ log.Fatal("Image must be paletted")
+ }
+ if len(cm.(color.Palette)) > 16 {
+ log.Fatal("Palette must be 16-color or less")
+ }
+
+ return img.(image.PalettedImage)
+}
+
+func findAllEncodeLengths(pixels []uint8, steps int) []packet.PacketRun {
+ results := make([]packet.PacketRun, 0)
+ if len(pixels) == 0 {
+ return results
+ }
+
+ for _, scan := range(scanFuncs) {
+ pkt := scan(pixels)
+ if pkt == nil {
+ continue
+ }
+ pkt_length := pkt.Length()
+ pkt_bytes := pkt.ByteLength()
+ if steps > 1 && len(pixels) > pkt_length {
+ rec_results := findAllEncodeLengths(pixels[pkt_length:], steps - 1)
+ for _, r := range(rec_results) {
+ results = append(results, packet.PacketRun{r.Length + pkt_length, r.Bytes + pkt_bytes, r.Depth + 1, pkt})
+ }
+ } else {
+ results = append(results, packet.PacketRun{pkt_length, pkt_bytes, 1, pkt})
+ }
+ }
+
+ return results
+}
+
+func findOptimalEncoding(pixels []uint8, optimize int) packet.Packet {
+ results := findAllEncodeLengths(pixels, optimize)
+ sort.Sort(packet.ByPacketEfficiency(results))
+ /*
+ fmt.Printf("optimal encodings (%d bytes remain):\n", len(pixels))
+ for _, v := range(results) {
+ fmt.Println(v)
+ }
+ */
+ return results[0].Head
+}
+
+func findRepeats(packetlist []packet.Packet) []packet.Packet {
+ outlist := make([]packet.Packet, 1, len(packetlist))
+ outlist[0] = packetlist[0]
+
+ for i := 1; i < len(packetlist); {
+ pkt := packet.ScanRepeat(packetlist, i)
+ if pkt != nil {
+ outlist = append(outlist, pkt)
+ rpkt := pkt.(*packet.RepeatPacket)
+ i += rpkt.Count()
+ } else {
+ outlist = append(outlist, packetlist[i])
+ i++
+ continue
+ }
+ }
+
+ return outlist
+}
+
+func (self *BitSmash) unpackRepeat() []packet.Packet {
+ outlist := make([]packet.Packet, 1)
+ outlist[0] = self.packetList[0]
+
+ c := 1
+ for _, p := range(self.packetList) {
+ switch p.(type) {
+ case *packet.RepeatPacket:
+ rp := p.(*packet.RepeatPacket)
+ outlist = rp.UnRepeat(outlist, c)
+ c += rp.Count()
+ default:
+ outlist = append(outlist, p)
+ c++
+ }
+ }
+
+ return outlist
+}
+
+func getPixelList(img image.PalettedImage) []uint8 {
+ p := img.(*image.Paletted)
+
+ return p.Pix
+}
+
+func NewFromPixels(pixels []uint8, size int, optimize int) BitSmash {
+ highest_color := byte(0)
+ for _, p := range(pixels) {
+ if p > highest_color {
+ highest_color = p
+ }
+ }
+
+ bs := BitSmash{
+ size,
+ 0,
+ false,
+ uint(highest_color + 1),
+ make([]packet.Packet, 0, 1),
+ }
+
+ i := 0
+ for i < len(pixels) {
+ packet := findOptimalEncoding(pixels[i:], optimize)
+ i += packet.Length()
+ bs.packetList = append(bs.packetList, packet)
+ }
+
+ bs.packetList = findRepeats(bs.packetList)
+
+ return bs
+}
+
+func NewFromImage(filename string, optimize int) BitSmash {
+ image := loadImage(filename)
+ size := image.Bounds().Size().X
+ return NewFromPixels(getPixelList(image), size, optimize)
+}
+
+func (self *BitSmash) Size() image.Point {
+ return image.Point{self.size, self.Length() / self.size}
+}
+
+func (self *BitSmash) Length() int {
+ n := 0
+ for _, p := range(self.packetList) {
+ n += p.Length()
+ }
+ return n
+}
+
+func (self *BitSmash) ByteLength() int {
+ n_pd := int(math.Ceil(float64(len(self.packetList)) / 4.0))
+ total_len := n_pd + 3
+ for _, p := range(self.packetList) {
+ total_len += p.ByteLength()
+ }
+ return total_len
+}
+
+func (self *BitSmash) packetType(n int) int {
+ switch self.packetList[n].(type) {
+ case *packet.RLEPacket:
+ return 0
+ case *packet.BinaryPatternPacket:
+ return 1
+ case *packet.DirectPacket:
+ return 2
+ case *packet.RepeatPacket:
+ return 3
+ }
+ return -1
+}
+
+func NewFromBSFile(filename string) BitSmash {
+ bs := BitSmash{
+ 0,
+ 0,
+ false,
+ 0,
+ nil,
+ }
+
+ file, err := os.Open(filename)
+ defer file.Close()
+ if err != nil {
+ log.Fatal(fmt.Sprintf("Failed to open: %v", err))
+ }
+ err = bs.ReadFrom(file)
+ if err != nil {
+ log.Fatal(fmt.Sprintf("Reading file: %v", err))
+ }
+
+ return bs
+}
+
+func (self *BitSmash) codecManagerInit(c ac.CodecManager) {
+ c.AddModel(packet.CONTEXT_PACKET_TYPE, ac.NewModelOrder0(4))
+ c.AddModel(packet.CONTEXT_COLOR, ac.NewModelOrder0(self.n_colors))
+ c.AddModel(packet.CONTEXT_PATTERN_NUMBER, ac.NewModelOrder0PreBias(16, packet.ContextBias(packet.CONTEXT_PATTERN_NUMBER)))
+ c.AddModel(packet.CONTEXT_PATTERN_REPEAT, ac.NewModelOrder0PreBias(8, packet.ContextBias(packet.CONTEXT_PATTERN_REPEAT)))
+ c.AddModel(packet.CONTEXT_RLE_REPEAT, ac.NewModelOrder0(16))
+ c.AddModel(packet.CONTEXT_REPEAT_DISTANCE, ac.NewModelOrder0PreBias(32, packet.ContextBias(packet.CONTEXT_REPEAT_DISTANCE)))
+ c.AddModel(packet.CONTEXT_REPEAT_LENGTH, ac.NewModelOrder0PreBias(8, packet.ContextBias(packet.CONTEXT_REPEAT_LENGTH)))
+}
+
+func (self *BitSmash) ReadFrom(file io.Reader) error {
+ var header [3]byte
+ n, err := file.Read(header[:])
+ if n < 3 {
+ log.Fatal("Short read on header")
+ } else if err != nil {
+ return err
+ }
+ self.size = sizes[int(header[0]) & 0x7]
+ self.palette = (int(header[0]) >> 3) & 0xF
+ self.transparent = ((header[0] >> 7) & 0x1) == 1
+
+ n_packets := int(header[1]) + (int(header[2]) & 0x3) + 1
+ self.n_colors = (uint(header[2]) >> 2) & 0xF
+ self.packetList = make([]packet.Packet, n_packets)
+
+ decoder, err := ac.NewDecoder(file)
+ if err != nil {
+ return err
+ }
+ self.codecManagerInit(decoder)
+
+ for i := 0; i < n_packets; i++ {
+ var pkt packet.Packet // Packet! PACKET! PACKET!!!
+ packet_type := decoder.Decode(packet.CONTEXT_PACKET_TYPE)
+ switch packet_type {
+ case 0:
+ pkt = packet.DecodeRLE(decoder)
+ case 1:
+ pkt = packet.DecodeBinaryPattern(decoder)
+ case 2:
+ pkt = packet.DecodeDirect(decoder)
+ case 3:
+ pkt = packet.DecodeRepeat(decoder)
+ }
+ self.packetList[i] = pkt
+ }
+ return nil
+}
+
+func (self *BitSmash) WriteTo(file io.Writer) error {
+ n_packets := len(self.packetList)
+ if n_packets > 1024 {
+ fmt.Println("Too many packets:", n_packets)
+ return errors.New("Too many packets")
+ }
+
+ var header [3]byte
+ transparent := 0
+ if (self.transparent) {
+ transparent = 1
+ }
+ header[0] = byte(sizeIndex(self.size) + (self.palette << 3) + (transparent << 7))
+ header[1] = byte((n_packets - 1) & 0xFF)
+ header[2] = byte(((n_packets - 1) >> 8) & 0x3 + (int(self.n_colors) << 2))
+
+ file.Write(header[:])
+
+ encoder, err := ac.NewEncoder(file)
+ if err != nil {
+ return err
+ }
+ self.codecManagerInit(encoder)
+
+ for i, p := range(self.packetList) {
+ encoder.Encode(packet.CONTEXT_PACKET_TYPE, uint32(self.packetType(i)))
+ p.Encode(encoder)
+ }
+ encoder.Finish()
+
+ return nil
+}
+
+func (self *BitSmash) Dump() {
+ self.unpackRepeat()
+ size := self.Size()
+ fmt.Printf("%d pixels, %d colors, %dx%d\n", self.Length(), self.n_colors, size.X, size.Y)
+ fmt.Printf("%d packets:\n", len(self.packetList))
+
+ c := 0
+
+ for _, p := range(self.packetList) {
+ switch p.(type) {
+ case *packet.RepeatPacket:
+ fmt.Printf(" %s\n", p)
+ rp := p.(*packet.RepeatPacket)
+ //d := c - rp.Distance()
+ //tpl = rp.UnRepeat(tpl, c)
+ for i := 0; i < rp.Count(); i++ {
+ fmt.Printf("%-4d %s\n", c + i, rp.Slice()[i])
+ }
+ c += rp.Count()
+ default:
+ fmt.Printf("%-4d %s\n", c, p)
+ c++
+ }
+ }
+
+ fmt.Printf("%d total bytes\n", self.ByteLength())
+}
+
+func (self *BitSmash) RawDump() {
+ for i, p := range(self.packetList) {
+ fmt.Printf("%-4d %s\n", i, p)
+ }
+}
+package main
+
+import (
+ "bytes"
+ "os"
+ "fmt"
+ "flag"
+ "encoding/base64"
+)
+
+type BitsmashOpts struct {
+ decode bool
+ dump bool
+ base64 bool
+ files []string
+ opt int
+}
+
+func parseArgs() BitsmashOpts {
+ bo := BitsmashOpts{}
+ flag.BoolVar(&bo.decode, "decode", false, "Decode from bitsmash input rather than encode image")
+ flag.BoolVar(&bo.dump, "dump", false, "dump detailed information about encoding")
+ flag.BoolVar(&bo.base64, "base64", false, "Encode the result with base64")
+ flag.IntVar(&bo.opt, "o", 3, "Optimization level")
+ flag.Parse()
+ bo.files = flag.Args()
+ return bo
+}
+
+func main() {
+ args := parseArgs()
+ if len(args.files) == 0 {
+ fmt.Println("Please specify a file to smash")
+ os.Exit(1)
+ }
+
+ var smash BitSmash
+ if (args.decode) {
+ smash = NewFromBSFile(args.files[0])
+ } else {
+ smash = NewFromImage(args.files[0], args.opt)
+ }
+
+ if args.dump {
+ smash.Dump()
+ } else {
+ var buf bytes.Buffer
+ smash.WriteTo(&buf)
+ if args.base64 {
+ fmt.Println(":_", base64.RawStdEncoding.EncodeToString(buf.Bytes()))
+ } else {
+ buf.WriteTo(os.Stdout)
+ }
+ }
+}
+package packet
+
+import (
+ "fmt"
+ "sort"
+ "strings"
+
+ "bytex64.net/code/bitsmash/ac"
+)
+
+var patterns [][]uint8 = [][]uint8{
+ {0, 1, 1, 1, 0},
+ {0, 1, 1, 1, 1},
+ {0, 0, 1, 1, 1},
+ {0, 0, 0, 1, 1},
+ {0, 0, 0, 0, 1},
+ {0, 1, 0, 1},
+ {0, 1, 1, 1},
+ {0, 1, 1, 0},
+ {0, 0, 0, 1},
+ {0, 0, 1, 0},
+ {0, 1, 0, 0},
+ {0, 0, 1, 1},
+ {0, 0, 1},
+ {0, 1, 1},
+ {0, 1, 0},
+ {0, 1},
+}
+
+type binaryPatternMatch struct {
+ Length int
+ Pattern uint8
+ Repeat uint8
+}
+
+type byPatternLength []binaryPatternMatch
+
+func (a byPatternLength) Len() int {
+ return len(a)
+}
+
+func (a byPatternLength) Swap(i, j int) {
+ a[i], a[j] = a[j], a[i]
+}
+
+func (a byPatternLength) Less(i, j int) bool {
+ return a[j].Length < a[i].Length
+}
+
+type BinaryPatternPacket struct {
+ c1, c2 uint8
+ pattern uint8
+ repeat uint8
+}
+
+func (self *BinaryPatternPacket) Length() int {
+ return len(patterns[self.pattern]) * (int(self.repeat) + 1)
+}
+
+func (*BinaryPatternPacket) ByteLength() int {
+ return 2
+}
+
+func (self *BinaryPatternPacket) Encode(encoder ac.CodecManager) {
+ encoder.Encode(CONTEXT_PATTERN_NUMBER, uint32(self.pattern))
+ encoder.Encode(CONTEXT_PATTERN_REPEAT, uint32(self.repeat))
+ encoder.Encode(CONTEXT_COLOR, uint32(self.c1))
+ encoder.Encode(CONTEXT_COLOR, uint32(self.c2))
+}
+
+func DecodeBinaryPattern(decoder ac.CodecManager) Packet {
+ pattern := byte(decoder.Decode(CONTEXT_PATTERN_NUMBER))
+ repeat := byte(decoder.Decode(CONTEXT_PATTERN_REPEAT))
+ c1 := byte(decoder.Decode(CONTEXT_COLOR))
+ c2 := byte(decoder.Decode(CONTEXT_COLOR))
+ return &BinaryPatternPacket{c1, c2, pattern, repeat}
+}
+
+func (self *BinaryPatternPacket) Pixels() []uint8 {
+ px := make([]uint8, self.Length())
+ patternLength := len(patterns[self.pattern])
+ c := []uint8{self.c1, self.c2}
+
+ for i := 0; i < int(self.repeat) + 1; i++ {
+ for j := 0; j < patternLength; j++ {
+ px[i * patternLength + j] = c[patterns[self.pattern][j]]
+ }
+ }
+ return px
+}
+
+func (self *BinaryPatternPacket) String() string {
+ patternbit := make([]string, len(patterns[self.pattern]))
+ for i, v := range(patterns[self.pattern]) {
+ patternbit[i] = fmt.Sprintf("%d", v)
+ }
+ patternstr := strings.Join(patternbit, "")
+
+ return fmt.Sprintf("BinaryPattern colors (%d, %d) pattern %s repeat %d", self.c1, self.c2, patternstr, self.repeat)
+}
+
+func findBinaryPattern(pixels []uint8) (uint8, uint8, []uint8) {
+ pat := []uint8{0}
+ a := pixels[0]
+ i := 1
+
+ for i < len(pixels) && pixels[i] == a {
+ pat = append(pat, 0)
+ i++
+ }
+
+ if i == len(pixels) {
+ return 0, 0, nil
+ }
+
+ b := pixels[i]
+ for i < len(pixels) && (pixels[i] == a || pixels[i] == b) {
+ if pixels[i] == a {
+ pat = append(pat, 0)
+ } else if pixels[i] == b {
+ pat = append(pat, 1)
+ }
+ i++
+ }
+
+ return a, b, pat
+}
+
+func patternPrefixMatch(needle []uint8, haystack []uint8) bool {
+ if len(haystack) < len(needle) {
+ return false
+ }
+ for i := 0; i < len(needle); i++ {
+ if haystack[i] != needle[i] {
+ return false
+ }
+ }
+ return true
+}
+
+func ScanBinaryPattern(pixels []uint8) Packet {
+ if len(pixels) < 2 {
+ return nil
+ }
+
+ c1, c2, pat := findBinaryPattern(pixels)
+ if pat == nil {
+ return nil
+ }
+
+ potential_matches := make([]binaryPatternMatch, 0)
+ for i, p := range(patterns) {
+ l := len(p)
+ repeat := 0
+ // If this pattern matches the prefix of the found pattern
+ if patternPrefixMatch(p, pat) {
+ // Find a repeat of this match
+ j := l
+ for patternPrefixMatch(p, pat[j:]) && repeat < 7 {
+ repeat++
+ j += l
+ }
+ potential_matches = append(potential_matches, binaryPatternMatch{l * (repeat + 1), uint8(i), uint8(repeat)})
+ }
+ }
+ if len(potential_matches) == 0 {
+ return nil
+ }
+
+ // Select longest match
+ sort.Sort(byPatternLength(potential_matches))
+ best_match := potential_matches[0]
+ if best_match.Length < 5 {
+ return nil
+ }
+
+ return &BinaryPatternPacket{c1, c2, best_match.Pattern, best_match.Repeat}
+}
+package packet
+
+import (
+ "fmt"
+
+ "bytex64.net/code/bitsmash/ac"
+)
+
+type DirectPacket struct {
+ c1, c2 uint8
+}
+
+func (*DirectPacket) Length() int {
+ return 2
+}
+
+func (*DirectPacket) ByteLength() int {
+ return 1
+}
+
+func (self *DirectPacket) Encode(encoder ac.CodecManager) {
+ encoder.Encode(CONTEXT_COLOR, uint32(self.c1))
+ encoder.Encode(CONTEXT_COLOR, uint32(self.c2))
+}
+
+func DecodeDirect(decoder ac.CodecManager) Packet {
+ c1 := byte(decoder.Decode(CONTEXT_COLOR))
+ c2 := byte(decoder.Decode(CONTEXT_COLOR))
+ return &DirectPacket{c1, c2}
+}
+
+func (self *DirectPacket) Pixels() []uint8 {
+ return []uint8{self.c1, self.c2}
+}
+
+func (self *DirectPacket) String() string {
+ return fmt.Sprintf("Direct colors (%d, %d)", self.c1, self.c2)
+}
+
+func ScanDirect(pixels []uint8) Packet {
+ var p [2]uint8
+ // This will still succeed even if only one pixel is available. The
+ // second pixel will be zero
+ copy(p[:], pixels[:])
+ return &DirectPacket{p[0], p[1]}
+}
+package packet
+
+import "bytex64.net/code/bitsmash/ac"
+
+const (
+ CONTEXT_PACKET_TYPE = ac.ModelContext(iota)
+ CONTEXT_COLOR
+ CONTEXT_PATTERN_NUMBER
+ CONTEXT_PATTERN_REPEAT
+ CONTEXT_RLE_REPEAT
+ CONTEXT_REPEAT_DISTANCE
+ CONTEXT_REPEAT_LENGTH
+)
+
+func ContextBias(context ac.ModelContext) []uint32 {
+ switch context {
+ case CONTEXT_PATTERN_NUMBER:
+ // Slight bias towards larger patterns
+ return []uint32{3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1}
+ case CONTEXT_PATTERN_REPEAT:
+ // Bias towards low numbers. Most common repeats are 0, 1, and 2.
+ return []uint32{8, 6, 3, 1, 1, 1, 1, 1}
+ case CONTEXT_REPEAT_DISTANCE:
+ // Slight bias to distances 1-8, but mostly everything is weighted to prevent too much shift
+ return []uint32{
+ 3, 3, 3, 3, 3, 3, 3, 3,
+ 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2,
+ }
+ case CONTEXT_REPEAT_LENGTH:
+ // Bias shorter lengths. Length 1 is actually fairly uncommon because
+ // we assume it isn't worth repeating a single packet in most cases.
+ return []uint32{1, 10, 8, 4, 2, 2, 2, 2}
+ default:
+ panic("Unsupported model context")
+ }
+}
+package packet
+
+import "bytex64.net/code/bitsmash/ac"
+
+type Packet interface {
+ Length() int
+ ByteLength() int
+ Encode(ac.CodecManager)
+ Pixels() []uint8
+ String() string
+}
+
+type PacketRun struct {
+ Length int
+ Bytes int
+ Depth int
+ Head Packet
+}
+
+type ByPacketEfficiency []PacketRun
+
+func (a ByPacketEfficiency) Len() int {
+ return len(a)
+}
+
+func (a ByPacketEfficiency) Swap(i, j int) {
+ a[i], a[j] = a[j], a[i]
+}
+
+func (a ByPacketEfficiency) Less(i, j int) bool {
+ e1 := float64(a[i].Length) / float64(a[i].Bytes)
+ e2 := float64(a[j].Length) / float64(a[j].Bytes)
+ if e1 == e2 {
+ if a[i].Depth == a[j].Depth {
+ return a[j].Head.Length() < a[i].Head.Length()
+ } else {
+ return a[i].Depth < a[j].Depth
+ }
+ } else {
+ return e1 > e2
+ }
+}
+package packet
+
+import (
+ "fmt"
+ "reflect"
+
+ "bytex64.net/code/bitsmash/ac"
+)
+
+type RepeatPacket struct {
+ distance uint8
+ packetSlice []Packet
+}
+
+func (self *RepeatPacket) Length() int {
+ c := 0
+ for _, p := range(self.packetSlice) {
+ c += p.Length()
+ }
+ return 0
+}
+
+func (*RepeatPacket) ByteLength() int {
+ return 1
+}
+
+func (self *RepeatPacket) Encode(encoder ac.CodecManager) {
+ encoder.Encode(CONTEXT_REPEAT_DISTANCE, uint32(self.distance - 1))
+ encoder.Encode(CONTEXT_REPEAT_LENGTH, uint32(self.Count() - 1))
+}
+
+func DecodeRepeat(decoder ac.CodecManager) Packet {
+ distance := byte(decoder.Decode(CONTEXT_REPEAT_DISTANCE))
+ length := byte(decoder.Decode(CONTEXT_REPEAT_LENGTH))
+ return &RepeatPacket{distance + 1, make([]Packet, length + 1)}
+}
+
+func (self *RepeatPacket) Pixels() []uint8 {
+ pixels := make([]uint8, self.Length())
+ c := 0
+ for _, p := range(self.packetSlice) {
+ pp := p.Pixels()
+ copy(pixels[c:], pp)
+ c += len(pp)
+ }
+ return pixels
+}
+
+func (self *RepeatPacket) String() string {
+ return fmt.Sprintf("Repeat distance %d length %d", self.distance, len(self.packetSlice))
+}
+
+func (self *RepeatPacket) Count() int {
+ return len(self.packetSlice)
+}
+
+func (self *RepeatPacket) Distance() int {
+ return int(self.distance)
+}
+
+func (self *RepeatPacket) Slice() []Packet {
+ return self.packetSlice
+}
+
+func (self *RepeatPacket) UnRepeat(packets []Packet, head int) []Packet {
+ count := self.Count()
+ start := head - int(self.distance)
+
+ for i := range(self.packetSlice) {
+ packets = append(packets, packets[start + i])
+ }
+ self.packetSlice = packets[start:start + count]
+ return packets
+}
+
+type packetMatch struct {
+ Start int
+ Length int
+}
+
+func findMatch(packets []Packet, head int, start int) *packetMatch {
+ matchlen := 0
+ maxlen := len(packets) - head
+ if maxlen > 8 {
+ maxlen = 8
+ }
+
+ for ; matchlen < maxlen && reflect.DeepEqual(packets[start + matchlen], packets[head + matchlen]); matchlen++ {
+ }
+
+ if matchlen == 0 {
+ return nil
+ }
+
+ headbytelen := packets[head].ByteLength()
+ if headbytelen == 1 && matchlen < 2 {
+ // Not saving any space for a single byte packet if we're not matching
+ // at least two packets
+ return nil
+ }
+
+ return &packetMatch{start, matchlen}
+}
+
+func ScanRepeat(packets []Packet, head int) Packet {
+ if head == 0 {
+ // Won't find any repeats at the head of the list
+ return nil
+ }
+
+ start := head - 32
+ if start < 0 {
+ start = 0
+ }
+
+ var bestMatch *packetMatch
+ for i := head - 1; i >= start; i-- {
+ match := findMatch(packets, head, i)
+ if match == nil {
+ continue
+ }
+ if bestMatch == nil || match.Length > bestMatch.Length {
+ bestMatch = match
+ }
+ }
+ if (bestMatch == nil) {
+ return nil
+ }
+
+ return &RepeatPacket{uint8(head - bestMatch.Start), packets[bestMatch.Start:bestMatch.Start + bestMatch.Length]}
+}
+package packet
+
+import (
+ "fmt"
+
+ "bytex64.net/code/bitsmash/ac"
+)
+
+type RLEPacket struct {
+ color uint8
+ length uint8
+}
+
+func (self *RLEPacket) Length() int {
+ return int(self.length)
+}
+
+func (self *RLEPacket) ByteLength() int {
+ return 1
+}
+
+func (self *RLEPacket) Encode(encoder ac.CodecManager) {
+ encoder.Encode(CONTEXT_COLOR, uint32(self.color))
+ encoder.Encode(CONTEXT_RLE_REPEAT, uint32(self.length - 2))
+}
+
+func DecodeRLE(decoder ac.CodecManager) Packet {
+ color := byte(decoder.Decode(CONTEXT_COLOR))
+ length := byte(decoder.Decode(CONTEXT_RLE_REPEAT))
+ return &RLEPacket{color, length + 2}
+}
+
+func (self *RLEPacket) Pixels() []uint8 {
+ px := make([]uint8, self.length)
+ for i := 0; i < int(self.length); i++ {
+ px[i] = self.color
+ }
+ return px
+}
+
+func (self *RLEPacket) String() string {
+ return fmt.Sprintf("RLE color %d length %d", self.color, self.length)
+}
+
+func ScanRLE(pixels []uint8) Packet {
+ i := 1
+ var maxlen int
+ if len(pixels) > 17 {
+ maxlen = 17
+ } else {
+ maxlen = len(pixels)
+ }
+ for i < maxlen && pixels[i] == pixels[0] {
+ i++
+ }
+ if i > 2 {
+ return &RLEPacket{pixels[0], uint8(i)}
+ } else {
+ return nil
+ }
+}
+#!/usr/bin/perl
+use Time::HiRes qw/gettimeofday tv_interval/;
+use File::Find;
+use strict;
+
+=pod
+
+So it turns out the Weissman Score is a real formula. Who knew?
+
+ r log T_bar
+ W = alpha * ----- * ---------
+ r_bar log T
+
+Where r and T are the compression ratio of the target algorithm, and r_bar
+and T_bar are the same for a reference compressor (in our case, PNG). Alpha
+is a constant scaling factor.
+
+http://spectrum.ieee.org/view-from-the-valley/computing/software/a-madefortv-compression-metric-moves-to-the-real-world
+
+=cut
+
+my ($bs_total, $png_total, $uncompressed_total, $bs_time, $png_time, $t0);
+
+find({
+ wanted => sub {
+ next unless -f && /\.png$/;
+
+ $t0 = [gettimeofday];
+ my $bs_size = qx!$ENV{HOME}/go/bin/bitsmash $_ | wc -c!;
+ $bs_time += tv_interval($t0);
+
+ $uncompressed_total += qx!convert $_ rgb:- | wc -c!;
+
+ my $png_size = -s;
+ # So... we're being a bit shifty here by actually decoding a PNG and
+ # then encoding it again. We really should be working from an
+ # uncompressed source, but PNGs are handy (and bitsmash is decoding a PNG, too, so it's not unfair).
+
+ $t0 = [gettimeofday];
+ system qq!convert $_ png:- >/dev/null!;
+ $png_time += tv_interval($t0);
+
+ printf("%4.1f%% %-6d %-6d %s\n", ($bs_size / $png_size) * 100, $bs_size, $png_size, $_);
+ $bs_total += $bs_size;
+ $png_total += $png_size;
+ },
+ no_chdir => 1,
+}, @ARGV);
+
+printf("$uncompressed_total uncompressed bytes\n");
+printf("$bs_total bitsmash bytes, %.2f seconds\n", $bs_time);
+printf("$png_total PNG bytes, %.2f seconds\n", $png_time);
+printf("%.1f%% of PNG\n", ($bs_total/$png_total) * 100);
+
+my $r = $uncompressed_total / $bs_total;
+my $r_bar = $uncompressed_total / $png_total;
+my $alpha = 1.0;
+printf("Weissman score: %.2f\n", $alpha * ($r / $r_bar) * (log($png_time) / log($bs_time)));