CVS commit: othersrc/external/bsd/circa

["Alistair G. Crooks" <agc%netbsd.org@localhost>]

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