## Copyright (c) 2017 Christopher A. Taylor. All rights reserved. ## ## Redistribution and use in source and binary forms, with or without ## modification, are permitted provided that the following conditions are met: ## ## * Redistributions of source code must retain the above copyright notice, ## this list of conditions and the following disclaimer. ## * Redistributions in binary form must reproduce the above copyright notice, ## this list of conditions and the following disclaimer in the documentation ## and/or other materials provided with the distribution. ## * Neither the name of Leopard-RS nor the names of its contributors may be ## used to endorse or promote products derived from this software without ## specific prior written permission. ## ## THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" ## AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE ## IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ## ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE ## LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR ## CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF ## SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS ## INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN ## CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ## ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE ## POSSIBILITY OF SUCH DAMAGE. ## Leopard-RS ## MDS Reed-Solomon Erasure Correction Codes for Large Data in C ## ## Algorithms are described in LeopardCommon.h ## ## ## Inspired by discussion with: ## ## Sian-Jhen Lin : Author of {1} {3}, basis for Leopard ## Bulat Ziganshin : Author of FastECC ## Yutaka Sawada : Author of MultiPar ## ## ## References: ## ## {1} S.-J. Lin, T. Y. Al-Naffouri, Y. S. Han, and W.-H. Chung, ## "Novel Polynomial Basis with Fast Fourier Transform ## and Its Application to Reed-Solomon Erasure Codes" ## IEEE Trans. on Information Theory, pp. 6284-6299, November, 2016. ## ## {2} D. G. Cantor, "On arithmetical algorithms over finite fields", ## Journal of Combinatorial Theory, Series A, vol. 50, no. 2, pp. 285-300, 1989. ## ## {3} Sian-Jheng Lin, Wei-Ho Chung, "An Efficient (n, k) Information ## Dispersal Algorithm for High Code Rate System over Fermat Fields," ## IEEE Commun. Lett., vol.16, no.12, pp. 2036-2039, Dec. 2012. ## ## {4} Plank, J. S., Greenan, K. M., Miller, E. L., "Screaming fast Galois Field ## arithmetic using Intel SIMD instructions." In: FAST-2013: 11th Usenix ## Conference on File and Storage Technologies, San Jose, 2013 import pkg/upraises push: {.upraises: [].} ## ----------------------------------------------------------------------------- ## Build configuration import std/compilesettings import std/os import std/strutils type LeoDataPtr* {.importc: "const void* const*", bycopy.} = pointer const LeopardCmakeFlags {.strdefine.} = when defined(macosx): "-DCMAKE_BUILD_TYPE=Release -DENABLE_OPENMP=off" elif defined(windows): "-G\"MSYS Makefiles\" -DCMAKE_BUILD_TYPE=Release" else: "-DCMAKE_BUILD_TYPE=Release" LeopardDir {.strdefine.} = joinPath(currentSourcePath.parentDir.parentDir, "vendor", "leopard") buildDir = joinPath(querySetting(nimcacheDir), "vendor_leopard") LeopardHeader {.strdefine.} = "leopard.h" LeopardLib {.strdefine.} = joinPath(buildDir, "liblibleopard.a") LeopardCompilerFlags {.strdefine.} = when defined(macosx): "-I" & LeopardDir else: "-I" & LeopardDir & " -fopenmp" LeopardLinkerFlags {.strdefine.} = when defined(macosx): LeopardLib else: LeopardLib & " -fopenmp" LeopardExtraCompilerFlags {.strdefine.} = "" LeopardExtraLinkerFlags {.strdefine.} = "" static: if defined(windows): func pathUnix2Win(path: string): string = gorge("cygpath -w " & path.strip).strip func pathWin2Unix(path: string): string = gorge("cygpath " & path.strip).strip proc bash(cmd: varargs[string]): string = gorge(gorge("which bash").pathUnix2Win & " -c '" & cmd.join(" ") & "'") proc bashEx(cmd: varargs[string]): tuple[output: string, exitCode: int] = gorgeEx(gorge("which bash").pathUnix2Win & " -c '" & cmd.join(" ") & "'") let buildDirUnix = buildDir.pathWin2Unix leopardDirUnix = LeopardDir.pathWin2Unix if defined(LeopardRebuild): discard bash("rm -rf", buildDirUnix) if (bashEx("ls", LeopardLib.pathWin2Unix)).exitCode != 0: discard bash("mkdir -p", buildDirUnix) let cmd = @["cd", buildDirUnix, "&& cmake", leopardDirUnix, LeopardCmakeFlags, "&& make libleopard"] echo "\nBuilding Leopard-RS: " & cmd.join(" ") let (output, exitCode) = bashEx cmd echo output if exitCode != 0: discard bash("rm -rf", buildDirUnix) raise (ref Defect)(msg: "Failed to build Leopard-RS") else: if defined(LeopardRebuild): discard gorge "rm -rf " & buildDir if gorgeEx("ls " & LeopardLib).exitCode != 0: discard gorge "mkdir -p " & buildDir let cmd = "cd " & buildDir & " && cmake " & LeopardDir & " " & LeopardCmakeFlags & " && make libleopard" echo "\nBuilding Leopard-RS: " & cmd let (output, exitCode) = gorgeEx cmd echo output if exitCode != 0: discard gorge "rm -rf " & buildDir raise (ref Defect)(msg: "Failed to build Leopard-RS") {.passc: LeopardCompilerFlags & " " & LeopardExtraCompilerFlags.} {.passl: LeopardLinkerFlags & " " & LeopardExtraLinkerFlags.} {.pragma: leo, cdecl, header: LeopardHeader.} proc leoInit*(): cint {.leo, importcpp: "leo_init".} ## ------------------------------------------------------------------------------ ## Shared Constants / Datatypes ## Results # TODO: For some reason it's only possibly to use the enum with `ord` type LeopardResult* = enum LeopardCallInitialize = -7, ## Call leo_init() first LeopardPlatform = -6, ## Platform is unsupported LeopardInvalidInput = -5, ## A function parameter was invalid LeopardInvalidCounts = -4, ## Invalid counts provided LeopardInvalidSize = -3, ## Buffer size must be a multiple of 64 bytes LeopardTooMuchData = -2, ## Buffer counts are too high LeopardNeedMoreData = -1, ## Not enough recovery data received LeopardSuccess = 0 ## Operation succeeded ## Convert Leopard result to string proc leoResultString*(result: LeopardResult): cstring {.leo, importc: "leo_result_string".} ## ------------------------------------------------------------------------------ ## Encoder API ## ## leo_encode_work_count() ## ## Calculate the number of work_data buffers to provide to leo_encode(). ## ## The sum of original_count + recovery_count must not exceed 65536. ## ## Returns the work_count value to pass into leo_encode(). ## Returns 0 on invalid input. ## proc leoEncodeWorkCount*(originalCount: cuint; recoveryCount: cuint): cuint {.leo, importc: "leo_encode_work_count".} ## ## leo_encode() ## ## Generate recovery data. ## ## original_count: Number of original_data[] buffers provided. ## recovery_count: Number of desired recovery data buffers. ## buffer_bytes: Number of bytes in each data buffer. ## original_data: Array of pointers to original data buffers. ## work_count: Number of work_data[] buffers, from leo_encode_work_count(). ## work_data: Array of pointers to work data buffers. ## ## The sum of original_count + recovery_count must not exceed 65536. ## The recovery_count <= original_count. ## ## The buffer_bytes must be a multiple of 64. ## Each buffer should have the same number of bytes. ## Even the last piece must be rounded up to the block size. ## ## Let buffer_bytes = The number of bytes in each buffer: ## ## original_count = static_cast( ## ((uint64_t)total_bytes + buffer_bytes - 1) / buffer_bytes); ## ## Or if the number of pieces is known: ## ## buffer_bytes = static_cast( ## ((uint64_t)total_bytes + original_count - 1) / original_count); ## ## Returns Leopard_Success on success. ## The first set of recovery_count buffers in work_data will be the result. ## Returns other values on errors. ## proc leoEncode*( bufferBytes: uint64; originalCount: cuint; recoveryCount: cuint; workCount: cuint; originalData: LeoDataPtr; workData: ptr pointer): LeopardResult {.leo, importc: "leo_encode".} ## Number of bytes in each data buffer ## Number of original_data[] buffer pointers ## Number of recovery_data[] buffer pointers ## Number of work_data[] buffer pointers, from leo_encode_work_count() ## Array of pointers to original data buffers ## ## Array of work buffers ## ------------------------------------------------------------------------------ ## Decoder API ## ## leo_decode_work_count() ## ## Calculate the number of work_data buffers to provide to leoDecode(). ## ## The sum of original_count + recovery_count must not exceed 65536. ## ## Returns the work_count value to pass into leo_encode(). ## Returns 0 on invalid input. ## proc leoDecodeWorkCount*(originalCount: cuint; recoveryCount: cuint): cuint {.leo, importc: "leo_decode_work_count".} ## ## leoDecode() ## ## Decode original data from recovery data. ## ## buffer_bytes: Number of bytes in each data buffer. ## original_count: Number of original_data[] buffers provided. ## original_data: Array of pointers to original data buffers. ## recovery_count: Number of recovery_data[] buffers provided. ## recovery_data: Array of pointers to recovery data buffers. ## work_count: Number of work_data[] buffers, from leo_decode_work_count(). ## work_data: Array of pointers to recovery data buffers. ## ## Lost original/recovery data should be set to NULL. ## ## The sum of recovery_count + the number of non-NULL original data must be at ## least original_count in order to perform recovery. ## ## Returns Leopard_Success on success. ## Returns other values on errors. ## proc leoDecode*( bufferBytes: uint64; originalCount: cuint; recoveryCount: cuint; workCount: cuint; originalData: LeoDataPtr; recoveryData: LeoDataPtr; workData: ptr pointer): LeopardResult {.leo, importc: "leo_decode".} ## Number of bytes in each data buffer ## Number of original_data[] buffer pointers ## Number of recovery_data[] buffer pointers ## Number of buffer pointers in work_data[] ## Array of original data buffers ## Array of recovery data buffers ## Array of work data buffers