block.go - external/github.com/google/gofountain - Git at Google

 // Copyright 2014 Google Inc. All rights reserved.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 package fountain

 // A block represents a contiguous range of data being encoded or decoded,
 // or a block of coded data. Details of how the source text is split into blocks
 // is governed by the particular fountain code used.
 type block struct {
 	// Data content of this source or code block.
 	data []byte

 	// How many padding bytes this block has at the end.
 	padding int
 }

 // newBlock creates a new block with a given length. The block will initially be
 // all padding.
 func newBlock(len int) *block {
 	return &block{padding: len}
 }

 // length returns the length of the block in bytes. Counts data bytes as well
 // as any padding.
 func (b *block) length() int {
 	return len(b.data) + b.padding
 }

 func (b *block) empty() bool {
 	return b.length() == 0
 }

 // A common operation is to XOR entire code blocks together with other blocks.
 // When this is done, padding bytes count as 0 (that is XOR identity), and the
 // destination block will be modified so that its data is large enough to
 // contain the result of the XOR.
 func (b *block) xor(a block) {
 	if len(b.data) < len(a.data) {
 		var inc = len(a.data) - len(b.data)
 		b.data = append(b.data, make([]byte, inc)...)
 		if b.padding > inc {
 			b.padding -= inc
 		} else {
 			b.padding = 0
 		}
 	}

 	for i := 0; i < len(a.data); i++ {
 		b.data[i] ^= a.data[i]
 	}
 }

 // partitionBytes partitions an input text into a sequence of p blocks. The
 // sizes of the blocks will be given by the partition() function. The last
 // block may have padding.
 // Return values: the slice of longer blocks, the slice of shorter blocks.
 // Within each block slice, all will have uniform lengths.
 func partitionBytes(in []byte, p int) ([]block, []block) {
 	sliceIntoBlocks := func(in []byte, num, length int) ([]block, []byte) {
 		blocks := make([]block, num)
 		for i := range blocks {
 			if len(in) > length {
 				blocks[i].data, in = in[:length], in[length:]
 			} else {
 				blocks[i].data, in = in, []byte{}
 			}
 			if len(blocks[i].data) < length {
 				blocks[i].padding = length - len(blocks[i].data)
 			}
 		}
 		return blocks, in
 	}

 	lenLong, lenShort, numLong, numShort := partition(len(in), p)
 	long, in := sliceIntoBlocks(in, numLong, lenLong)
 	short, _ := sliceIntoBlocks(in, numShort, lenShort)
 	return long, short
 }

 // equalizeBlockLengths adds padding to all short blocks to make them equal in
 // size to the long blocks. The caller should ensure that all the longBlocks
 // have the same length.
 // Returns a block slice containing all the long and short blocks.
 func equalizeBlockLengths(longBlocks, shortBlocks []block) []block {
 	if len(longBlocks) == 0 {
 		return shortBlocks
 	}
 	if len(shortBlocks) == 0 {
 		return longBlocks
 	}

 	for i := range shortBlocks {
 		shortBlocks[i].padding += longBlocks[0].length() - shortBlocks[i].length()
 	}

 	blocks := make([]block, len(longBlocks)+len(shortBlocks))
 	copy(blocks, longBlocks)
 	copy(blocks[len(longBlocks):], shortBlocks)
 	return blocks
 }

 // sparseMatrix is the block decoding data structure. It is a sparse matrix of
 // XOR equations. The coefficients are the indices of the source blocks which
 // are XORed together to produce the values. So if equation _i_ of the matrix is
 // block_0 ^ block_2 ^ block_3 ^ block_9 = [0xD2, 0x38]
 // that would be represented as coeff[i] = [0, 2, 3, 9], v[i].data = [0xD2, 0x38]
 // Example: The sparse coefficient matrix
 // | 0 1 1 0 |
 // | 0 1 0 0 |
 // | 0 0 1 1 |
 // | 0 0 0 1 |
 // would be represented as
 // [ [ 1, 2],
 //   [ 1 ],
 //   [ 2, 3],
 //   [ 3 ]]
 // Every row has M[i][0] >= i. If we added components [2] to this matrix, it
 // would replace the M[2] row ([2, 3]), and then the resulting component vector
 // after cancellation against that row ([3]) would be used instead of the
 // original equation. In this case, M[3] is already populated, so the new
 // equation is redundant (and could be used for ECC, theoretically), but if we
 // didn't have an entry in M[3], it would be placed there.
 // The values were omitted from this discussion, but they follow along by doing
 // XOR operations as the components are reduced during insertion.
 type sparseMatrix struct {
 	coeff [][]int
 	v     []block
 }

 // xorRow performs a reduction of the given candidate equation (indices, b)
 // with the specified matrix row (index s). It does so by XORing the values,
 // and then taking the symmetric difference of the coefficients of that matrix
 // row and the provided indices. (That is, the "set XOR".) Assumes both
 // coefficient slices are sorted.
 func (m *sparseMatrix) xorRow(s int, indices []int, b block) ([]int, block) {
 	b.xor(m.v[s])

 	var newIndices []int
 	coeffs := m.coeff[s]
 	var i, j int
 	for i < len(coeffs) && j < len(indices) {
 		index := indices[j]
 		if coeffs[i] == index {
 			i++
 			j++
 		} else if coeffs[i] < index {
 			newIndices = append(newIndices, coeffs[i])
 			i++
 		} else {
 			newIndices = append(newIndices, index)
 			j++
 		}
 	}

 	newIndices = append(newIndices, coeffs[i:]...)
 	newIndices = append(newIndices, indices[j:]...)
 	return newIndices, b
 }

 // addEquation adds an XOR equation to the decode matrix. The online decode
 // strategy is a variant of that of Bioglio, Grangetto, and Gaeta
 // (http://www.di.unito.it/~bioglio/Papers/CL2009-lt.pdf) It maintains the
 // invariant that either coeff[i][0] == i or len(coeff[i]) == 0. That is, while
 // adding an equation to the matrix, it ensures that the decode matrix remains
 // triangular.
 func (m *sparseMatrix) addEquation(components []int, b block) {
 	// This loop reduces the incoming equation by XOR until it either fits into
 	// an empty row in the decode matrix or is discarded as redundant.
 	for len(components) > 0 && len(m.coeff[components[0]]) > 0 {
 		s := components[0]
 		if len(components) >= len(m.coeff[s]) {
 			components, b = m.xorRow(s, components, b)
 		} else {
 			// Swap the existing row for the new one, reduce the existing one and
 			// see if it fits elsewhere.
 			components, m.coeff[s] = m.coeff[s], components
 			b, m.v[s] = m.v[s], b
 		}
 	}

 	if len(components) > 0 {
 		m.coeff[components[0]] = components
 		m.v[components[0]] = b
 	}
 }

 // Check to see if the decode matrix is fully specified. This is true when
 // all rows have non-empty coefficient slices.
 // TODO(gbillock): is there a weakness here if an auxiliary block is unpopulated?
 func (m *sparseMatrix) determined() bool {
 	for _, r := range m.coeff {
 		if len(r) == 0 {
 			return false
 		}
 	}
 	return true
 }

 // reduce performs Gaussian Elimination over the whole matrix. Presumes
 // the matrix is triangular, and that the method is not called unless there is
 // enough data for a solution.
 // TODO(gbillock): Could profitably do this online as well?
 func (m *sparseMatrix) reduce() {
 	for i := len(m.coeff) - 1; i >= 0; i-- {
 		for j := 0; j < i; j++ {
 			ci, cj := m.coeff[i], m.coeff[j]
 			for k := 1; k < len(cj); k++ {
 				if cj[k] == ci[0] {
 					m.v[j].xor(m.v[i])
 					continue
 				}
 			}
 		}
 		// All but the leading coefficient in the rows have been reduced out.
 		m.coeff[i] = m.coeff[i][0:1]
 	}
 }

 // reconstruct pastes the fully reduced values in the sparse matrix result column
 // into a new byte array and returns it. The length/number parameters are typically
 // those given by partition().
 // lenLong is how many long blocks there are.
 // lenShort is how many short blocks there are (following the long blocks).
 // numLong is how many bytes are in the long blocks.
 // numShort is how many bytes the short blocks are.
 func (m *sparseMatrix) reconstruct(totalLength, lenLong, lenShort, numLong, numShort int) []byte {
 	out := make([]byte, totalLength)
 	out = out[0:0]
 	for i := 0; i < numLong; i++ {
 		out = append(out, m.v[i].data[0:lenLong]...)
 	}
 	for i := numLong; i < numLong+numShort; i++ {
 		out = append(out, m.v[i].data[0:lenShort]...)
 	}

 	return out
 }
	// Copyright 2014 Google Inc. All rights reserved.
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	package fountain

	// A block represents a contiguous range of data being encoded or decoded,
	// or a block of coded data. Details of how the source text is split into blocks
	// is governed by the particular fountain code used.
	type block struct {
	// Data content of this source or code block.
	data []byte

	// How many padding bytes this block has at the end.
	padding int
	}

	// newBlock creates a new block with a given length. The block will initially be
	// all padding.
	func newBlock(len int) *block {
	return &block{padding: len}
	}

	// length returns the length of the block in bytes. Counts data bytes as well
	// as any padding.
	func (b *block) length() int {
	return len(b.data) + b.padding
	}

	func (b *block) empty() bool {
	return b.length() == 0
	}

	// A common operation is to XOR entire code blocks together with other blocks.
	// When this is done, padding bytes count as 0 (that is XOR identity), and the
	// destination block will be modified so that its data is large enough to
	// contain the result of the XOR.
	func (b *block) xor(a block) {
	if len(b.data) < len(a.data) {
	var inc = len(a.data) - len(b.data)
	b.data = append(b.data, make([]byte, inc)...)
	if b.padding > inc {
	b.padding -= inc
	} else {
	b.padding = 0
	}
	}

	for i := 0; i < len(a.data); i++ {
	b.data[i] ^= a.data[i]
	}
	}

	// partitionBytes partitions an input text into a sequence of p blocks. The
	// sizes of the blocks will be given by the partition() function. The last
	// block may have padding.
	// Return values: the slice of longer blocks, the slice of shorter blocks.
	// Within each block slice, all will have uniform lengths.
	func partitionBytes(in []byte, p int) ([]block, []block) {
	sliceIntoBlocks := func(in []byte, num, length int) ([]block, []byte) {
	blocks := make([]block, num)
	for i := range blocks {
	if len(in) > length {
	blocks[i].data, in = in[:length], in[length:]
	} else {
	blocks[i].data, in = in, []byte{}
	}
	if len(blocks[i].data) < length {
	blocks[i].padding = length - len(blocks[i].data)
	}
	}
	return blocks, in
	}

	lenLong, lenShort, numLong, numShort := partition(len(in), p)
	long, in := sliceIntoBlocks(in, numLong, lenLong)
	short, _ := sliceIntoBlocks(in, numShort, lenShort)
	return long, short
	}

	// equalizeBlockLengths adds padding to all short blocks to make them equal in
	// size to the long blocks. The caller should ensure that all the longBlocks
	// have the same length.
	// Returns a block slice containing all the long and short blocks.
	func equalizeBlockLengths(longBlocks, shortBlocks []block) []block {
	if len(longBlocks) == 0 {
	return shortBlocks
	}
	if len(shortBlocks) == 0 {
	return longBlocks
	}

	for i := range shortBlocks {
	shortBlocks[i].padding += longBlocks[0].length() - shortBlocks[i].length()
	}

	blocks := make([]block, len(longBlocks)+len(shortBlocks))
	copy(blocks, longBlocks)
	copy(blocks[len(longBlocks):], shortBlocks)
	return blocks
	}

	// sparseMatrix is the block decoding data structure. It is a sparse matrix of
	// XOR equations. The coefficients are the indices of the source blocks which
	// are XORed together to produce the values. So if equation _i_ of the matrix is
	// block_0 ^ block_2 ^ block_3 ^ block_9 = [0xD2, 0x38]
	// that would be represented as coeff[i] = [0, 2, 3, 9], v[i].data = [0xD2, 0x38]
	// Example: The sparse coefficient matrix
	// \| 0 1 1 0 \|
	// \| 0 1 0 0 \|
	// \| 0 0 1 1 \|
	// \| 0 0 0 1 \|
	// would be represented as
	// [ [ 1, 2],
	// [ 1 ],
	// [ 2, 3],
	// [ 3 ]]
	// Every row has M[i][0] >= i. If we added components [2] to this matrix, it
	// would replace the M[2] row ([2, 3]), and then the resulting component vector
	// after cancellation against that row ([3]) would be used instead of the
	// original equation. In this case, M[3] is already populated, so the new
	// equation is redundant (and could be used for ECC, theoretically), but if we
	// didn't have an entry in M[3], it would be placed there.
	// The values were omitted from this discussion, but they follow along by doing
	// XOR operations as the components are reduced during insertion.
	type sparseMatrix struct {
	coeff [][]int
	v []block
	}

	// xorRow performs a reduction of the given candidate equation (indices, b)
	// with the specified matrix row (index s). It does so by XORing the values,
	// and then taking the symmetric difference of the coefficients of that matrix
	// row and the provided indices. (That is, the "set XOR".) Assumes both
	// coefficient slices are sorted.
	func (m *sparseMatrix) xorRow(s int, indices []int, b block) ([]int, block) {
	b.xor(m.v[s])

	var newIndices []int
	coeffs := m.coeff[s]
	var i, j int
	for i < len(coeffs) && j < len(indices) {
	index := indices[j]
	if coeffs[i] == index {
	i++
	j++
	} else if coeffs[i] < index {
	newIndices = append(newIndices, coeffs[i])
	i++
	} else {
	newIndices = append(newIndices, index)
	j++
	}
	}

	newIndices = append(newIndices, coeffs[i:]...)
	newIndices = append(newIndices, indices[j:]...)
	return newIndices, b
	}

	// addEquation adds an XOR equation to the decode matrix. The online decode
	// strategy is a variant of that of Bioglio, Grangetto, and Gaeta
	// (http://www.di.unito.it/~bioglio/Papers/CL2009-lt.pdf) It maintains the
	// invariant that either coeff[i][0] == i or len(coeff[i]) == 0. That is, while
	// adding an equation to the matrix, it ensures that the decode matrix remains
	// triangular.
	func (m *sparseMatrix) addEquation(components []int, b block) {
	// This loop reduces the incoming equation by XOR until it either fits into
	// an empty row in the decode matrix or is discarded as redundant.
	for len(components) > 0 && len(m.coeff[components[0]]) > 0 {
	s := components[0]
	if len(components) >= len(m.coeff[s]) {
	components, b = m.xorRow(s, components, b)
	} else {
	// Swap the existing row for the new one, reduce the existing one and
	// see if it fits elsewhere.
	components, m.coeff[s] = m.coeff[s], components
	b, m.v[s] = m.v[s], b
	}
	}

	if len(components) > 0 {
	m.coeff[components[0]] = components
	m.v[components[0]] = b
	}
	}

	// Check to see if the decode matrix is fully specified. This is true when
	// all rows have non-empty coefficient slices.
	// TODO(gbillock): is there a weakness here if an auxiliary block is unpopulated?
	func (m *sparseMatrix) determined() bool {
	for _, r := range m.coeff {
	if len(r) == 0 {
	return false
	}
	}
	return true
	}

	// reduce performs Gaussian Elimination over the whole matrix. Presumes
	// the matrix is triangular, and that the method is not called unless there is
	// enough data for a solution.
	// TODO(gbillock): Could profitably do this online as well?
	func (m *sparseMatrix) reduce() {
	for i := len(m.coeff) - 1; i >= 0; i-- {
	for j := 0; j < i; j++ {
	ci, cj := m.coeff[i], m.coeff[j]
	for k := 1; k < len(cj); k++ {
	if cj[k] == ci[0] {
	m.v[j].xor(m.v[i])
	continue
	}
	}
	}
	// All but the leading coefficient in the rows have been reduced out.
	m.coeff[i] = m.coeff[i][0:1]
	}
	}

	// reconstruct pastes the fully reduced values in the sparse matrix result column
	// into a new byte array and returns it. The length/number parameters are typically
	// those given by partition().
	// lenLong is how many long blocks there are.
	// lenShort is how many short blocks there are (following the long blocks).
	// numLong is how many bytes are in the long blocks.
	// numShort is how many bytes the short blocks are.
	func (m *sparseMatrix) reconstruct(totalLength, lenLong, lenShort, numLong, numShort int) []byte {
	out := make([]byte, totalLength)
	out = out[0:0]
	for i := 0; i < numLong; i++ {
	out = append(out, m.v[i].data[0:lenLong]...)
	}
	for i := numLong; i < numLong+numShort; i++ {
	out = append(out, m.v[i].data[0:lenShort]...)
	}

	return out
	}