-
Notifications
You must be signed in to change notification settings - Fork 8
/
interface.go
194 lines (156 loc) · 8.32 KB
/
interface.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
/*
raptorq package provides the RaptorQ encoder/decoder and their factory
interfaces, as well as a few concrete factory implementations.
In order to send a binary object, termed “source object,” the sender creates an
Encoder for the source object. The Encoder first splits the source object into
one or more contiguous blocks, termed “source blocks,” then for each source
block, the Encoder generates encoded and serially numbered chunks of data,
termed “encoding symbols.” For each source block, the sender uses the Encoder
to generate as many encoding symbols as needed by the receiver to recover the
source block. The sender chooses the size of the encoding symbol, in octets,
when creating an Encoder.
On the other side, the receiver creates a Decoder for the same source object,
then keeps feeding the Decoder with the encoding symbols received from the
sender, until the Decoder is able to recover the source object from the
encoding symbols. Once the source object has been recovered, the receiver
closes and discards the Decoder.
An encoding symbol is a unit data of transmission. Each encoding symbol is
identified by a (SBN, ESI) pair, where SBN is the 8-bit serial number of the
source block from which the symbol was generated, and ESI is the 24-bit serial
identifier of the encoding symbol within the source block. Both SBN and ESI are
zero-based.
Upon receipt of an encoding symbol, the receiver first needs to identify the
Decoder to use for the source object to which the received encoding symbol
belongs, then feed the Decoder with the encoding symbol, along with its SBN and
ESI.
In order to recover each source block with high probability, the receiver needs
as many encoding symbols as needed to fulfill the original size (in octets) of
the source block. For example, a 1MiB source block with 1KiB encoding symbols,
the receiver would need 1024 encoding symbols with 99% probability. Each
additional symbol adds roughly “two nines” to the decoding success probability:
In the example above, 1025 encoding symbols would mean 99.99%, and 1026 encoding
symbols would mean 99.9999%.
It is okay for an encoding symbol to be completely lost (erased) during
transit. For each encoding symbol lost, the encoder simply needs to generate
and send another encoding symbol. The sender need not know which encoding
symbol was lost; a brand new encoding symbol would be able to replace for any
previously sent-and-lost encoding symbol. The sender may even anticipate losses
and send additional encoding symbols in advance without having to wait for
negative acknowledgements (NAKs) from the receiver.
(Proactively sending redundant symbols this way is called forward error
correction (FEC), and is useful to reduce or even eliminate round-trip delays
required for reliable object transmission. It can be seen as a form of
“insurance,” with the amount of extra, redundant data being its “insurance
premium.”)
It is NOT okay for an encoding symbol to be corrupted—accidentally or
maliciously—during transit. Feeding a Decoder with such corrupted symbols WILL
jeopardize recovery of the source object, so the receiver MUST detect and
discard corrupted encoding symbols, e.g. using checksums calculated and
transmitted by the sender along with the encoding symbol.
The Encoder and Decoder for the same source object should share the following
information: Total source object size (in octets), symbol size (chosen by the
sender), number of source blocks, number of sub-blocks (an internal detail), and
the symbol alignment factor (another internal detail). The IETF Forward Error
Correction (FEC) Building Block specification (RFC 5052) and the RaptorQ
specification (RFC 6330) encapsulate these into two parameters: 64-bit Common
FEC Object Transmission Information, and 32-bit Scheme-Specific FEC Object
Transmission Information. They are available from the sender's Encoder; the
receiver should pass them when creating a Decoder.
*/
package raptorq
// Encoder encodes one object into a series of symbols.
type Encoder interface {
// Encode writes the encoding symbol identified by the given source block
// number and encoding symbol ID, into the given buffer.
//
// On success, Encode returns the number of octets written into buf and nil
// error.
//
// On error, Encode returns a non-nil error code.
Encode(sbn uint8, esi uint32, buf []byte) (written uint, err error)
// CommonOTI returns the Common FEC Object Transmission Information.
CommonOTI() uint64
// SchemeSpecificOTI returns the RaptorQ Scheme-Specific FEC Object
// Transmission Information.
SchemeSpecificOTI() uint32
// TransferLength returns the source object size, in octets. “F” in RFC
// 6330.
TransferLength() uint64
// SymbolSize returns the symbol size, in octets. “T” in RFC 6330.
SymbolSize() uint16
// NumSourceBlocks returns the number of source blocks. “Z” in RFC 6330.
NumSourceBlocks() uint8
// NumSubBlocks returns the number of sub-blocks. “N” in RFC 6330.
NumSubBlocks() uint8
// SymbolAlignmentParameter returns the symbol alignment, in octets. “Al”
// in RFC 6330.
SymbolAlignmentParameter() uint8
// MaxSubBlockSize returns the maximum size block that is decodable in
// working memory, in octets. “WS” in RFC 6330.
MaxSubBlockSize() uint32
// NumBlocks returns the number of blocks.
NumBlocks() uint8
// Free, on supported implementations, will free memory used for generating
// encoding symbols for the given source block. Once a source block has
// been freed, calling Encode with its SBN may return an error.
FreeSourceBlock(sbn uint8)
// SourceBlockSize returns the size of the given source block, in bytes, or
// 0 if sbn is out of range.
SourceBlockSize(sbn uint8) uint32
// NumSourceSymbols returns the number of encoding symbols covering the
// original source data in the given source block, or 0 if sbn is out of
// range. The first encoding symbols up to this number is called source
// symbols, and contains the source block data itself.
NumSourceSymbols(sbn uint8) uint16
// MinSymbols returns the minimum number of encoding symbols needed to
// achieve the 99% probability of decoding the given source block,
// or 0 if sbn is out of range. “K” in RFC 6330.
MinSymbols(sbn uint8) uint16
// MaxSymbols returns the maximum number of encoding symbols the encoder
// can generate for the given source block, or 0 if sbn is out of range.
MaxSymbols(sbn uint8) uint32
// Close closes the Encoder. After an Encoder is closed, all methods but
// Close() will panic if called.
Close() error
}
// EncoderFactory is a factory of Encoder instances.
type EncoderFactory interface {
/*
NewEncoder creates and returns an Encoder that can encode the given
source object into symbols.
input is the source object to encode.
symbolSize is the encoding symbol size, in octets.
minSubSymbolSize is the minimum encoding symbol size allowed, in octets.
(If you are not sure, or if you do not want internal interleaving of
source symbols, set it equal to symbolSize.)
maxSubBlockSize is the maximum size block that is decodable in working
memory, in octets. Iff this is lower than the source object size, the
source object will be split into more than one source blocks. The
maximum allowed value is 56403 * symbolSize.
alignment is an internal alignment parameter, in bytes. Typically this
is a power of 2, up to implementation-defined maximum. Larger alignment
will speed up calculation, at the expense of slightly higher
transmission size overhead. Both symbolSize and minSubSymbolSize must
be a multiple of this.
On success, NewEncoder returns an Encoder instance and nil error; on
failure, it returns nil Encoder and an error code.
*/
New(input []byte, symbolSize uint16, minSubSymbolSize uint16,
maxSubBlockSize uint32, alignment uint8) (enc Encoder, err error)
}
// TODO ek - below
// Decoder decodes encoding symbols and reconstructs one object into a series of
// symbols.
type Decoder interface {
}
// DecoderFactory is a factory of Decoder instances.
type DecoderFactory interface {
/*
NewDecoder creates and returns a Decoder that can decode incoming source
symbols and recover the original source object.
commonOTI is the Common FEC Object Transmission Information, received
from the sender's encoder.
schemeSpecificOTI is the Scheme-Specific FEC Object Transmission
Information, sent by
*/
}