Testing ISA-L RS Vand Invertibility

rs_vand.go

package main

/*
#cgo CFLAGS: -I/usr/local/include
#cgo LDFLAGS: /usr/local/lib/libisal.a
#include <stdlib.h>
#include <string.h>
#include <isa-l.h>
*/
import "C"
import "fmt"
import "sync"
import "unsafe"

func genPermutations(n int, r int) <-chan []int {
	out := make(chan []int)
	go func() {
		defer close(out)
		pool := make([]int, n)
		indices := make([]int, r)
		for i := 0; i < n; i = i + 1 {
			pool[i] = i
			if i < r {
				indices[i] = i
			}
		}
		res := make([]int, r)
		for i, j := range indices {
			res[i] = pool[j]
		}
		out <- res
		for {
			var stop = true
			for i := r - 1; i >= 0; i = i - 1 {
				if indices[i] != i+n-r {
					indices[i] += 1
					for j := i + 1; j < r; j = j + 1 {
						indices[j] = indices[j-1] + 1
					}
					stop = false
					break
				}
			}
			if stop {
				return
			}
			res := make([]int, r)
			for i, j := range indices {
				res[i] = pool[j]
			}
			out <- res
		}
	}()
	return out
}

func getOffset(ptr *C.uchar, index int) unsafe.Pointer {
	base := uintptr(unsafe.Pointer(ptr))
	offset := uintptr(index) * unsafe.Sizeof(*ptr)
	return unsafe.Pointer(base + offset)
}

func checkPermutations(k int, m int, matrix *C.uchar, permutations <-chan []int) <-chan bool {
	out := make(chan bool)
	go func() {
		defer close(out)
		for perm := range permutations {
			dec_matrix := (*C.uchar)(C.malloc(C.size_t(k * k)))
			for i, v := range perm {
				C.memcpy(getOffset(dec_matrix, k*i), getOffset(matrix, k*v), C.size_t(k))
			}
			inv_matrix := (*C.uchar)(C.malloc(C.size_t(k * k)))
			res := (C.gf_invert_matrix(dec_matrix, inv_matrix, C.int(k)) == 0)
			out <- res
			C.free(unsafe.Pointer(inv_matrix))
			C.free(unsafe.Pointer(dec_matrix))
		}
	}()
	return out
}

func merge(cs ...<-chan bool) <-chan bool {
	var wg sync.WaitGroup
	out := make(chan bool)

	// Start an output goroutine for each input channel in cs.  output
	// copies values from c to out until c is closed, then calls wg.Done.
	output := func(c <-chan bool) {
		for r := range c {
			out <- r
		}
		wg.Done()
	}
	wg.Add(len(cs))
	for _, c := range cs {
		go output(c)
	}

	// Start a goroutine to close out once all the output goroutines are
	// done.  This must start after the wg.Add call.
	go func() {
		wg.Wait()
		close(out)
	}()
	return out
}

func checkAll(k int, m int) bool {
	matrix := (*C.uchar)(C.malloc(C.size_t(k * (k + m))))
	//defer C.free(unsafe.Pointer(matrix))
	C.gf_gen_cauchy1_matrix(matrix, C.int(k+m), C.int(k))
	//C.gf_gen_rs_matrix(matrix, C.int(k+m), C.int(k))

	perms := genPermutations(k+m, k)

	w1 := checkPermutations(k, m, matrix, perms)
	w2 := checkPermutations(k, m, matrix, perms)
	w3 := checkPermutations(k, m, matrix, perms)
	w4 := checkPermutations(k, m, matrix, perms)
	w5 := checkPermutations(k, m, matrix, perms)
	w6 := checkPermutations(k, m, matrix, perms)
	w7 := checkPermutations(k, m, matrix, perms)
	w8 := checkPermutations(k, m, matrix, perms)

	for res := range merge(w1, w2, w3, w4, w5, w6, w7, w8) {
		if !res {
			C.free(unsafe.Pointer(matrix))
			return false
		}
	}
	C.free(unsafe.Pointer(matrix))
	return true
}

func main() {
	maxK := 31
	maxM := 31

	fmt.Print("   ")
	for m := 0; m <= maxM; m = m + 1 {
		fmt.Printf("%2d ", m)
	}
	for k := 1; k <= maxK; k = k + 1 {
		fmt.Printf("\n%2d ", k)
		for m := 0; m <= maxM; m = m + 1 {
			if k+m > 32 {
				continue
			}

			if checkAll(k, m) {
				fmt.Print("   ")
				//fmt.Printf("%2d + %2d: OK\n", k, m)
			} else {
				fmt.Print(" ✗ ")
				//fmt.Printf("%2d + %2d: FAIL\n", k, m)
			}
		}
	}
}