Skip to content

Instantly share code, notes, and snippets.

@whyrusleeping
Created September 15, 2014 01:36
Show Gist options
  • Save whyrusleeping/a9f1b4435d07483ee654 to your computer and use it in GitHub Desktop.
Save whyrusleeping/a9f1b4435d07483ee654 to your computer and use it in GitHub Desktop.
broken code
package rabin
import (
"bufio"
"bytes"
"crypto/rand"
"fmt"
"io"
"testing"
)
func ThisMightBeRabin(r io.Reader) chan []byte {
out := make(chan []byte)
go func() {
// Buffer input
inbuf := bufio.NewReader(r)
blkbuf := new(bytes.Buffer)
// Some random bullshit numbers i made up
a := 10
mask := 0xfff
MOD := 33554383
windowSize := 16
an := 1
rollingHash := 0
// Window is a circular buffer
window := make([]byte, windowSize)
get := func(i int) int { return int(window[i%len(window)]) }
set := func(i int, val byte) { window[i%len(window)] = val }
// Read in window length
i := 0
for ; i < windowSize; i++ {
b, err := inbuf.ReadByte()
if err != nil {
fmt.Println(err)
return
}
blkbuf.WriteByte(b)
window[i] = b
rollingHash = (rollingHash*a + int(b)) % MOD
an = (an * a) % MOD
}
// Compute rolling hashes
for ; true; i++ {
b, err := inbuf.ReadByte()
if err != nil {
break
}
outval := get(i)
set(i, b)
blkbuf.WriteByte(b)
rollingHash = (rollingHash*a + get(i) - an*outval) % MOD
if rollingHash&mask == mask {
fmt.Printf("sending buf: %v\n", blkbuf.Bytes()[:16])
out <- blkbuf.Bytes()
blkbuf.Reset()
}
peek, err := inbuf.Peek(windowSize)
if err != nil || len(peek) != windowSize {
break
}
}
io.Copy(blkbuf, inbuf)
fmt.Printf("sending last buf: %v\n", blkbuf.Bytes()[:16])
out <- blkbuf.Bytes()
close(out)
}()
return out
}
func TestRabinSplit(t *testing.T) {
// Generate some random data
nbytes := 256 * 4096
buf := new(bytes.Buffer)
io.CopyN(buf, rand.Reader, int64(nbytes))
good := buf.Bytes()
// Get Block Generator for random data
ch := ThisMightBeRabin(buf)
i := 0
var blocks [][]byte
for blk := range ch {
fmt.Printf("got block: %v\n", blk[:16])
if !bytes.Equal(blk, good[i:len(blk)+i]) {
t.Fatalf("bad block! %v", blk[:16])
} else {
fmt.Println("GOOD BLOCK MATE!")
}
i += len(blk)
blocks = append(blocks, blk)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment