Module Name: othersrc Committed By: agc Date: Sat May 7 02:31:24 UTC 2011
Update of /cvsroot/othersrc/external/bsd/circa In directory ivanova.netbsd.org:/tmp/cvs-serv4077 Log Message: Initial import of libcirca(3) and circa(1) into othersrc. The circa(3) library encodes data, protecting against damage in transit or at rest. The data size expands by 4/3 to provide protection. The library is based loosely on the protection scheme used by CD-ROMs, and employs two Reed-Solomon erasure codings (one inner and one outer), and a number of dispersal, delay lines and scattering of bytes. There are numerous areas in which single bit errors can cause re-transmission of large amounts of data, or cause file system data errors - encoding with libcirca(3) can protect against this. To illustrate its use: % wc dist/circa.h 81 425 2898 dist/circa.h % circa -o h2 dist/circa.h % hd h2 | grep n | wc -l 101 % sed -e 's|n|o|g' h2 > h2e % hd h2e | grep n | wc -l 0 % hd h2e | grep o | wc -l 157 % circa -d -o h3 h2e % diff dist/circa.h h3 % i.e. circa(1) can recover completely from all 101 instances of the 'n' character being transformed into 'o', in a file of 2898 characters. (hd is a shell alias for the "codecs hexdump" transformation described elsewhere). Taken from the libcirca(3) man page: DESCRIPTION The libcirca library implements a number of functions designed to protect data against errors and erasures. It uses a number of methods of doing this, and is loosely based on Cross-Interleaved Reed-Solomon Coding, as found in CDs. The libcirca draws heavily on the librs(3) library inter- nally. The aim of this library is to encode data in preparation for transmission or storage. Various erasure codes and checksums are added to the origi- nal data, in an effort to recover the original data in the face of errors in individual bits and bytes in the encoded data. This is the same idea as implemented in CD CIRC encoding. Internally, two Reed-Solomon erasure codes are employed, a 28,24 erasure code acting on the original data, and a 32,28 erasure code acting on the output from that. The net effect of these two erasure codes is that the size of the encoded data increases by (32 / 24) or (4 / 3) The circa_init() function should be called prior to using the encoding and decoding functions. circa_encode() is used to encode data so that it is protected against data corruption. It returns the number of bytes produced in the out array. To decode the original data, circa_decode() is called. When creating output files, the two functions circa_get_header() and circa_put_header() are used. INTERNALS The libcirca library performs a number of transformations, when encoding data. These transformations are modelled on the Cross Interleaved Reed-Solomon Coding as used in CDs. Delay lines can straddle sectors in CIRC encoding for CDs, whilst libcirca strictly keeps all sector data within the same sector. This has implications about integrity of data cross-sector, although other means, such as libthreshold(3) and libssss(3) can be used to replicate data at a sector level, to say noth- ing of protection by other means such as RAID raid(4). A default sector is 3136 bytes in length, although this can be changed at circa_init() time with the sectorsize argument. Each 24 bytes of input data is transformed into 32 bytes of encoded data. The 24 bytes of input data is known as a C3 frame, and the 32 bytes of encoded data is known as a C1 frame. The transformations are, in encoding order: delay1 Every other 4 bytes in the input stream are put into a delay slot of 1 frame. scramble Within a C3 frame, the bytes are changed to occupy different positions. This is done to mitigate the problem where a number of bytes next to each other are the subject of errors. Q-Parity A Reed Solomon 28,24 erasure code is calculated over the 24 bytes of the C3 frame. This erasure code is inserted at the half-way point of the C3 frame. This creates a C2 frame of 28 bytes. Dispersal Each bytes is striped across the sector, according to the byte offset from the start of the C2 frame. Byte b in C2 frame f will end up in frame (f + b) and byte b in the output sector. P-Parity A Reed Solomon 32,28 erasure code is calculated on the C2 frame, to create a 32-byte C1 frame. delay2 Even bytes are delayed 1 frame in the output. At decoding time, the transformations to the bytes occur in the opposite order. The circa(1) utility is also provided to encode and decode data. Another example of its use is provided below: % circa Makefile > Makefile.circa % hd Makefile.circa | head -20 00000 | 00 a0 4c c1 40 0c 00 00 00 5a 31 74 63 31 00 fd | ..L.@....Z1tc1.. 00016 | 00 00 00 00 00 35 00 3f 00 00 00 63 7f 00 00 7d | .....5.?...c...} 00032 | 00 00 00 00 ac 5c e4 9c 37 00 00 0a 61 49 00 00 | .......7...aI.. 00048 | 42 00 00 00 7e 32 99 00 63 00 00 64 00 00 00 00 | B...~2..c..d.... 00064 | 55 00 00 00 fd 1d 05 71 00 20 9f 24 20 17 31 00 | U......q. .$ .1. 00080 | 2f fd 00 ff 52 00 16 00 63 00 00 52 00 00 00 00 | /...R...c..R.... 00096 | 69 4d 00 00 c3 9a 12 cc 97 20 70 2e 28 c1 61 2e | iM....... p.(.a. 00112 | 24 53 60 66 af 00 7d 00 20 00 00 00 69 00 00 00 | $S`f..}. ...i... 00128 | 69 36 00 00 af 71 b1 84 76 63 57 55 90 6b 69 67 | i6...q..vcWU.kig 00144 | 49 30 ff 3a a3 00 ff 00 20 20 00 00 34 00 00 00 | I0.:.... ..4... 00160 | 7d 42 00 00 22 18 74 74 36 75 64 74 00 00 c0 72 | }B..".tt6udt...r 00176 | 73 0a 65 2b ea 00 c2 00 41 20 00 00 3d 00 00 00 | s.e+....A ..=... 00192 | 00 72 00 00 4e 20 0f 72 62 09 43 00 00 00 00 65 | .r..N .rb.C....e 00208 | 52 54 35 0a 64 c2 0c 00 00 20 00 00 2e 00 00 00 | RT5.d.... ...... 00224 | 00 72 00 00 2c 1e 13 5f 6c 24 20 00 00 00 00 00 | .r..,.._l$ ..... 00240 | 40 75 52 3e 22 e9 f1 3c 00 61 00 00 0a 6c 00 00 | @uR>"..<.a...l.. 00256 | 00 2f 65 00 38 b9 86 3b 0a 00 00 00 00 00 00 00 | ./e.8..;........ 00272 | c0 44 0a 63 00 54 63 e2 00 3c 00 00 61 31 00 00 | .D.c.Tc..<..a1.. 00288 | 00 00 3a 00 09 69 9d 52 20 00 00 00 00 00 00 00 | ..:..i.R ....... 00304 | 00 00 6b 00 00 41 ad 27 00 24 00 00 00 20 00 00 | ..k..A.'.$... .. % sed -e 's|M|N|g' Makefile.circa > Makefile.damaged % cmp Makefile.circa Makefile.damaged Makefile.circa Makefile.damaged differ: char 98, line 2 % circa -d -o Makefile.recon Makefile.damaged % diff Makefile Makefile.recon % Status: Vendor Tag: CROOKS Release Tags: circa-base N othersrc/external/bsd/circa/Makefile N othersrc/external/bsd/circa/tst N othersrc/external/bsd/circa/dist/libcirca.3 N othersrc/external/bsd/circa/dist/Makefile N othersrc/external/bsd/circa/dist/circa.1 N othersrc/external/bsd/circa/dist/main.c N othersrc/external/bsd/circa/dist/circa.c N othersrc/external/bsd/circa/dist/circa.h N othersrc/external/bsd/circa/circa/Makefile N othersrc/external/bsd/circa/libcirca/Makefile N othersrc/external/bsd/circa/libcirca/shlib_version No conflicts created by this import