master
1package ltcodes
2
3import "math/rand"
4import "fmt"
5import "math"
6import "bytes"
7
8type Packet struct {
9 n int
10 degree int
11 seed int64
12 data []byte
13}
14
15type indexedPacket struct {
16 index []int
17 degree int
18 data []byte
19}
20
21func xorBytes(b ...[]byte) []byte {
22 b_len := len(b[0])
23 for _, m := range b {
24 if len(m) != b_len {
25 panic("length mismatch!")
26 }
27 }
28 br := make([]byte, b_len)
29 for i := range b[0] {
30 br[i] = 0
31 for _, m := range b {
32 br[i] = br[i] ^ m[i]
33 }
34 }
35 return br
36}
37
38func degreeGen(msg_len int, block_len int) int {
39 // returns 1 <= d <= msg_len - block_len
40 // TODO: implement "robust soliton distribution" here
41 return rand.Intn(msg_len-block_len-1) + 1
42}
43
44// create or reconstruct the list of source blocks that were used
45// to generate an encoded block
46func indexGen(degree int, seed int64, n_blocks int) []int {
47 psudo_seed := rand.NewSource(seed)
48 psudo_rng := rand.New(psudo_seed)
49 indices := make([]int, degree)
50 for i := 0; i < degree; i++ {
51 indices[i] = psudo_rng.Intn(n_blocks)
52 }
53 return indices
54}
55
56// Emit one encoded Packet from message msg and of length block_len
57// Packet return includes: generated degree (degree), index seed (seed),
58// number of blocks msg has been divided into (n), and the encoded data (data)
59func Encode(packets chan<- Packet, msg []byte, block_len int) Packet {
60 for {
61 // TODO: add check for erroneous block_len (relative to len(m))
62 n_blocks := len(msg) / block_len
63 degree := degreeGen(len(msg), block_len)
64 blocks := make([][]byte, degree)
65 seed := rand.Int63n(math.MaxInt64)
66 indices := indexGen(degree, seed, n_blocks)
67 for i, m := range indices {
68 blocks[i] = make([]byte, block_len)
69 blocks[i] = msg[m*block_len : (m*block_len + block_len)]
70 }
71 packets <- Packet{n: n_blocks, degree: degree, seed: seed, data: xorBytes(blocks...)}
72 }
73}
74
75// check if decoding complete
76func messageDecoded(message [][]byte) bool {
77 for _, v := range message {
78 if v == nil {
79 return false
80 }
81 }
82 return true
83}
84
85// translation from packet to indexedPacket type
86func indexPacket(p Packet) indexedPacket {
87 i := indexGen(p.degree, p.seed, p.n)
88 return indexedPacket{index: i, degree: p.degree, data: p.data}
89}
90
91// decrease the index of "packet" at index "i" by xoring in "clean_data"
92// return updated packet
93func reducePacket(i int, packet indexedPacket, clean_data []byte) indexedPacket {
94 packet.data = xorBytes(packet.data, clean_data)
95 packet.index = append(packet.index[:i], packet.index[i+1:]...)
96 packet.degree = packet.degree - 1
97 return packet
98}
99
100// check packet for index values that match up with clean ones (stored in message)
101// reduce packet if match found and return it
102func process(packet indexedPacket, message [][]byte) indexedPacket {
103 for i := 0; i < len(packet.index); i++ { //, m_i := range packet.index {
104 if message[packet.index[i]] != nil {
105 packet = reducePacket(i, packet, message[packet.index[i]])
106 }
107 }
108 return packet
109}
110
111// check clean data against buffer of unprocessed data
112func processClean(clean indexedPacket, buffer_area []indexedPacket, message [][]byte) ([][]byte, []indexedPacket) {
113 if len(clean.index) != 1 {
114 panic("received 'clean' of degree != 1")
115 }
116 clean_index := clean.index[0]
117 message[clean_index] = clean.data
118 if messageDecoded(message) {
119 return message, buffer_area
120 }
121
122 // loop over all buffered packets
123 for b_i := 0; b_i < len(buffer_area); b_i++ {
124 packet := buffer_area[b_i]
125
126 // loop over packet index
127 for i := 0; i < len(packet.index); i++ {
128
129 // if match, reduce packet
130 if clean_index == packet.index[i] {
131
132 // important to update packet (for loop needs it)
133 packet = reducePacket(i, packet, clean.data)
134 buffer_area[b_i] = packet
135
136 // check for and handle a new clean packet
137 if packet.degree == 1 {
138 buffer_area = append(buffer_area[:b_i], buffer_area[b_i+1:]...)
139 if message[packet.index[0]] == nil {
140 message, buffer_area = processClean(packet, buffer_area, message)
141 }
142 }
143 }
144 }
145 }
146 return message, buffer_area
147}
148
149// receive packets and combine them until message discovered
150func Decode(packets <-chan Packet, decodeDone chan<- bool) {
151
152 // get first packet and setup
153 p := <-packets
154 message := make([][]byte, p.n)
155 buffer_area := make([]indexedPacket, 1)
156 buffer_area[0] = indexPacket(p)
157 counter := 0
158
159 // packet receive loop
160 for {
161 p := indexPacket(<-packets)
162 counter++
163
164 if p.degree > 1 {
165 p = process(p, message)
166
167 if p.degree > 1 {
168 buffer_area = append(buffer_area, p)
169
170 } else if p.degree == 1 {
171 message, buffer_area = processClean(p, buffer_area, message)
172 }
173
174 } else if p.degree == 1 {
175 message, buffer_area = processClean(p, buffer_area, message)
176 }
177
178 if messageDecoded(message) {
179 fmt.Println("Packets:", counter)
180 outMsg := bytes.Join(message, []byte{})
181 fmt.Println("Packets / byte:", float64(counter)/float64(len(outMsg)))
182 decodeDone <- true
183 return
184 }
185 }
186}