<commit_before>Parity Volume Set Specificiation 3.0

<NAME>

Started January 16th, 2020


Based on Parity Volume Set Specification 1.0 [2001-10-14] by <NAME> and others.
Based on Parity Volume Set Specification 2.0 [2003-05-11] by <NAME> with ideas from <NAME>, <NAME>, and <NAME>


Introduction:

This document describes a file format for storing redundant data for a set of files.  If any of the original set of files is damaged in storage or transmission, the redundant data can be used to regenerate the original input.  Of course, not all damages can be repaired, but many can. 

In operation, a user will select a set of files from which the redundant data is to be made. These are known as "input files" and the set of them is known as the "recovery set". The user will provide these to a program which generates file(s) that match the specification in this document. The program is known as a "PAR 3.0 client" or "client" for short, and the generated files are known as "PAR 3.0 files" or "PAR files". If the files in the recovery set ever get damaged (e.g. when they are transmitted or stored on a faulty disk) the client can read the damaged input files, read the (possibly damaged) PAR files, and regenerate the original input files.  Again, not all damages can be repaired, but many can. 

In addition to being a file format, the Par 3.0 standard can be used as a network protocol for forward error correction.  Instead of files, data objects can be packaged in the Par 3.0 format and send over an unreliable channel, like UDP.  Redundant data can be generated and also sent over the channel.  The receiver can use the redundant data to recover data objects that experienced data loss.

In Par 3.0, the redundant data is calculated using any linear systematic code. This includes a wide variety of error correcting codes, including Reed-Solomon and many Low Density Parity Check (LDPC). This flexibility allows Par 3.0 clients to choose between speed and the number of errors that can be recovered.  It also allows Par 3.0 to support any codes whose patents expire or new codes that are developed.

During Par 3.0 file creation, the input files are chopped into equal-sized blocks known as "input slices".  If a file does not fill out the chunk, i.e. it ends mid-slice, the rest of the slice is treated as if it is padded with zero bytes.  Each slice is treated as an array of values in a "Galios Field", which is a mathematical concept that behaves like an unsigned integer with a strange/useful overflow behavior.  The redundant data is generated by multiplying data from each input slice by a matrix.  The redundant data is generated in the same equal-sized blocks, which are called "recovery slices".

Recovery is accomplished by subtracting the effect of every input slice that arrives intact, inverting the matrix, and then multiplying the recovery data from each recovery slice that arrived intact.  

The PAR 3.0 file itself is made of packets - self-contained parts with their own checksum. This design prevents damage to one part of the file from making the whole file unusable. 

Packets have a type and each type of packet serves a different purpose. One describes a file.  One describes the matrix.  Another contains the checksums of the slices in a file. And yet another contains a recovery slice.  There are a few other types too.

A PAR 3.0 file is only required to contain 1 specific packet - the packet that identifies the type of client that created the file. This way, if clients are creating files that don't match the specification in some way, they can be tracked down.

The packets can be packaged into multiple files. Files can contain duplicate packets - in fact, this is recommended for vital packets, such as the ones that describe the input files. Packets can appear in any order in a file, but there is a recommended order if you want to support clients that recover the file(s) in a single pass.  


Design Goals:

Par 3.0's goal is to provide a complete solution for the bottom two layers of archiving - redundant data and splitting.  The other layers are best supported by other programs (tar, zip/gzip/7zip, pgp/gpg, etc.).  Par 3.0 does provide minimal support for other layers, for ease and integration.  For example, it does support multiple input files.

Major differences from Par 2.0 are:
* support any systematic linear code (Reed-Solomon with Vandermonde matrix or Cauchy, LDPC, random sparse martix)
* support streaming / single-pass recovery
* support parity data inside a ZIP, ISO 9600, or other file

Part of supporting any linear code is to fix the major bug in Par 2.0, which is that it did not do Reed-Solomon encoding as it promised.  There was a major mistake in the paper that Par 2.0 relied on.  The problem manifested as a bug in Par 1.0 and, while Par 2.0 reduced its occurance, it did not fix the problem.  Par 2.0 did not use an always invertible matrix; it essentially used a random matrix, which (luckily) is invertible with high probability.  Par 3.0 fixes that bug.

Supporting new linear codes, like LDPC and sparse random matrices, will allow much faster Par file generation.

Some minor differences are:
* UTF-8 filenames (which were supported as a never-published Par 2.1 standard)
* support for recovery from multiple files with overlapping recovery sets
* the ability to change file names without regenerating all Par files
* empty directories
* more than 2^16 files

Par 3.0 drops explicit support for the non-recovery set.  It can be simulated by zero entries in the matrix.



Conventions

There are a number of conventions used in the design of this specification.

The data is 8-byte aligned. That is, every field starts on an index in the file which is congruent to zero, modulus 8. (That is, address % 8 == 0) This is because some memory systems function faster if 64-bit quantities are 8-byte aligned. It should be noted that a file could be corrupted (bytes inserted or deleted) to throw off the alignment. 

All integers in this version of the spec are unsigned integers of either 4 or 8 bytes in length.

Strings are not null-terminated. This is to prevent hackers from using stack-overflow attacks. In order to make a string 8-byte aligned, 1 to 7 zero bytes may be appended.  If an N-byte field contains an array, a null-terminated string can be created by copying the N-byte field into a character array of length N+1 and then the setting the N+1 character to '\0'.

The lengths of arrays and strings are often implicit. For example, if a region is known to be 32 bytes and that region contains an 8-byte integer and a string, then the string is known to take up 24 bytes. The string is then at least 17 bytes in length, since the 24 bytes contains 0 to 7 bytes of NUL padding at the end.

All strings are UTF-8.  

The lengths of files and parts of files are determined by 8-byte integers. This is to support OSes that can handle files longer than 4GB.

All integers are Intel-endian. (That is, little endian.)

The recovery set is identified by a 16-byte value known as the Recovery Set ID. Every part of the PAR file that affects a recovery set contains the recovery set ID. In this 3.0 version, the Recovery Set ID is a random number.  It is recommended that clients use the MD5 hash of a user identifier (account name), machine identifier (hostname, IP address, etc.) and a high-resolution clock.  The way of calculating this value could change in future versions; clients reading files should not rely on how it is calculated.

Files are also identified by a 16-byte value. In this 3.0 Version, it is an MD5 Hash of their length and the MD5 Hash of their first 16kB. The way of calculating this value could change in future versions; clients reading files should not rely on how it is calculated.

Every byte of a PAR file is specified. There are no places to throw junk bytes that can be any value. Padding, where needed, is specified to be zero bytes. The order of items in all arrays is specified.

The specification is designed so that if two clients generate a packet with the same parameters, the packets are identical (except for client-identifying or client-specific packets). Thus, client writers can compare the output of their program against the reference implementation by comparing packets byte-for-byte.




Description:

A PAR 3.0 file consists of a sequence of "packets". A packet has a fixed sized header and a variable length body. The packet header contains a checksum for the packet - if the packet is damaged, the packet is ignored. The packet header also contains a packet-type. If the client does not understand the packet type, the packet is ignored. To be compliant with this specification, a client must understand the "core" set of packets. Client may process the optional packets or create their own application-specific packets.

The packet header is:

Table: Packet Header
Length (bytes)	Type	Description
8	byte[8]	Magic sequence. Used to quickly identify location of packets. Value = {'P', 'A', 'R', '2', '\0', 'P', 'K', 'T'} (ASCII)
8	8-byte uint	Length of the entire packet. Must be multiple of 8. (NB: Includes length of header.)
16	MD5 Hash	MD5 Hash of packet. Used as a checksum for the packet. Calculation starts at first byte of Recovery Set ID and ends at last byte of body. Does not include the magic sequence, length field or this field. NB: The MD5 Hash, by its definition, includes the length as if it were appended to the packet.
16	MD5 Hash	Recovery Set ID. All packets that belong together have the same recovery set ID. (See "Conventions" for how it is calculated.)
16	byte[16]	Type. Can be anything. All beginning "PAR " (ASCII) are reserved for specification-defined packets. Application-specific packets are recommended to begin with the ASCII name of the client.
?*8	?	Body of Packet. Must be a multiple of 8 bytes.

There are various types of packets. The "core" set of packets - the set of packets that all clients must recognize and process - are listed next. For each, the value for the "type" field will be listed along with the contents of the body of the packet. 

It is important to notice that the Magic Sequence and, later, some Type fields refer to "PAR2".  This is because the packet header format and those particular packet types are also valid according to the PAR 2.0 file specification.  A PAR 2.0 client will be able to read them and do something with them, even if it could not use all the features introduced in this PAR 3.0 specification.


Creator packet

This packet is used to identify the client that created the file. It is required to be in every PAR file. If a client is unable to process a recovery set, the contents of the creator packet must be shown to the user. The goal of this is that any client incompatibilities can be found and resolved quickly.

The creator packet has a type value of "PAR 2.0\0Creator\0" (ASCII). The packet's body contains the following:

Table: Creator Packet Body Contents
Length (bytes)	Type	Description
?*8	UTF-8 char array	UTF-8 text identifying the client. This should also include a way to contact the client's creator - either through a URL or an email address. NB: This is not a null terminated string!

It is recommended that the text in the creator packet include any parameters used to generate the file.  For example, the command line arguments.  This will aid in debugging problems.


Matrix packet

This packet describes a Galois Field and matrix used to recover data.   

The creator packet has a type value of "PAR 3.0\0Matrix\0\0" (ASCII). The packet's body contains the following:

Table: Matrix Packet Body Contents
Length (bytes)	Type	Description
8	unsigned int	The size of the Galois field in bits.  Clients are only required to support values of 16.
8	unsigned int	The generator of the Galois field.  Clients are only required to support values generator 0x0001100B. 
?*8	various	
?*8	UTF-8 char array	UTF-8 text identifying the client. This should also include a way to contact the client's creator - either through a URL or an email address. NB: This is not a null terminated string!

It is recommended that the text in the creator packet include any parameters used to generate the file.  For example, the command line arguments.  This will aid in debugging problems.




File hash  (license, code, projects using, speed, ...)
  Blake3 :
    8 times faster than MD5, using single thread SSE, 16kB input
       ---> Blake3 paper says it is roughly the same speed, maybe a touch faster, than KangarooTwelve
       ---> same paper says it is much faster on an ARM (Raspberry Pi)
       ---> VERY multi-threadable
    Public Domain CC0 1.0
    Rust is default implementation; C doesn't use threads.
    GCC or MSVC
    256-bit output
  KangarooTwelve:
    Mostly Public Domain CC0
    Python or Rust or C<commit_msg>Draft of Par3 specification<commit_after>Parity Volume Set Specificiation 3.0

<NAME>

Started January 16th, 2020


Based on Parity Volume Set Specification 1.0 [2001-10-14] by <NAME> and others.
Based on Parity Volume Set Specification 2.0 [2003-05-11] by <NAME> with ideas from <NAME>, <NAME>, and <NAME>


Introduction:

This document describes a file format for storing redundant data for a set of files.  If any of the original files is damaged in storage or transmission, the redundant data can be used to regenerate the original input.  Of course, not all damages can be repaired, but many can. 

In operation, a user will select a set of files from which the redundant data is to be made.  These are known as "input files" and together they are known as the "input set". The user will provide these to a program which generates files that match the specification in this document.  The program is known as a "PAR 3.0 client" or "client" for short, and the generated files are known as "PAR 3.0 files" or "PAR files". If the files in the input set ever get damaged (e.g. when they are transmitted unreliably or stored on a faulty disk) the client can read the damaged input files, read the (possibly damaged) PAR files, and regenerate the original input files.  Again, not all damages can be repaired, but many can. 

In addition to being a file format, the Par 3.0 standard can be used as a network protocol for forward error correction.  Instead of files, data objects can be packaged in the Par 3.0 format and send over an unreliable channel, like UDP.  Redundant data can be generated and also sent over the channel.  The receiver can use the redundant data to recover data objects that experienced data loss.


Design Goals:

Par 3.0's goal is to provide a complete solution for the bottom two layers of archiving - redundant data and splitting.  The other layers are best supported by other programs (tar, zip/gzip/7zip, pgp/gpg, etc.).  Par 3.0 does provide minimal support for other layers, for ease and integration.  

Major differences from Par 2.0 are:
* support any systematic linear code (Reed-Solomon with Vandermonde matrix or Cauchy, LDPC, random sparse martix).
* support streaming / single-pass recovery.
* support files that work both as a PAR 3.0 file and another type.  For example, putting recovery data inside a ZIP, ISO 9600, or other file.

Part of "support any systematic linear code" is to fix the major bug in Par 2.0: it did not do Reed-Solomon encoding as it promised.  There was a major mistake in the paper that Par 2.0 relied on.  The problem manifested as a bug in Par 1.0 and, while Par 2.0 reduced its occurance, it did not fix the problem.  Par 2.0 did not use an always invertible matrix; it essentially used a random matrix, which (luckily) is invertible with high probability.  Par 3.0 fixes that bug.

The other part of "support any systematic linear code" is that non-Reed-Solomon codes can be much faster.  LDPC and sparse random matrices will speed things up dramatically, with a slight increase in errors that cannot be recovered from.

Some minor differences from Par 2.0 are:
* UTF-8 filenames (which were supported as a never-published Par 2.1 standard)
* support for recovery from multiple files with overlapping recovery sets
* the ability to change file names without regenerating every packet
* empty directories
* more than 2^16 files


The "Big Picture":

Par uses Linear Algebra to generate the redundant data and, after damage, to recover the original input data.  To understand its operation, you should be familiar with vectors, matrices, etc.

The calculation of redundant data starts with the input data being packaged into a set of vectors.  Those vectors are multiplied by the "code matrix" to generate vectors of redundant data.  Thus, a redundant vector "r" is equal to an input vector "i" times the code matrix "C".

r = iC

Recovery is accomplished by first identifying the good input data and good redundant data.  Good data is data that arrived intact; bad data was lost or damaged.  We can then partition of the elements of each vector into "good" ones and "bad" ones.  We can do the same for the elements of the code matrix.

r = | r_good |   i = | i_good |    C = | C_good,good C_good,bad | 
    | r_bad  |       | i_bad  |        | C_bad,good  C_bad,bad  |

| r_good | = r = iC = | i_good || C_good,good C_good,bad |
| r_bad  |            | i_bad  || C_bad,good  C_bad,bad  |            


Our goal, of cource, is to recover the bad input data.  To do that, we pull out the equation for the good redundant data...

r_good = i_good*C_good,good + i_bad*C_good,bad

... and solve for the bad input data.

i_bad = (r_good - i_good*C_good,good) C_good,bad^-1

Here, "^-1" indicates the right inverse of the matrix.  Since the redundant data is made by multiplying the input data by the code matrix, it's that inverse that allows us to recreate the missing input data from the redundant data.  Not every matrix has a right inverse.  When the right inverse does not exist, we cannot recover the input data.  A right inverse doesn't exist when it has more columns than rows, which means we cannot recover if there are more bad input blocks than good redundant blocks.  

Unlike your linear algebra class, the elements of the vectors and matrices are not integers nor reals, but elements of a "Galois Field".  Like the computer's integers, they come in various sizes like 8-bits, 16-bits, etc. and support operations called addition, subtraction, multiplication, and division.  Unlike the computer's integers, "division" exactly inverts "multiplication" for every value.  (Computer integers can overflow during multiplication, preventing division from inverting the multiplication.)

Par 3.0 improves on Par 2.0 by supporting multiple Galois Fields and by supporting any code matrix.  This means Par 3.0 supports a wide variety of error correcting codes known as "linear systematic codes".  These include Reed-Solomon and many Low Density Parity Check (LDPC) codes.  This flexibility allows Par 3.0 clients to choose between speed and the number of errors that can be recovered.  It also allows Par 3.0 to support any codes whose patents expire or new codes that are developed.


The "Detailed Picture":

Generating the recovery data starts with choosing a Galois Field and block size.  The Galois Field is usually chosen based on whatever is fastest for the computer.  For this example, I'll assume it fits in 2-bytes (16-bits).  The block size is the smallest unit for recovering data.  It is usually chosen to maximize speed and lower storage overhead.  The block size must be a multiple of the size of the Galois Field.  For this example, I'll assume it is 2048 bytes, but in practice it can be much larger, often megabytes.

Next, the input files are broken into block-sized pieces.  These are known as "input blocks".  If a file does not completely fill the block (that is, it ends in the middle of one), the rest of the block is treated as if it is padded with zero bytes.

The input blocks' data is then reorganized to make the input vectors.  The first Galois-field-sized part of each input block is used to make the elements of the first input vector.  In our example, the Galois Field size is 2 bytes, so the first 2 bytes of each input block becomes the elements of first input vector.  The 3rd and 4th bytes of each input block are used to make the elements of the second input vector.  Etc.  The number of input vectors is determined by the block size divided by the size of the Galois Field.  So, for this example, there are 2048/2 = 1024 input vectors.  The length of each input vector is equal to the number of input blocks.

Next, we choose the number of recovery blocks that we want. The number of recovery blocks determines the maximum number of damaged/missing input blocks that we can recover.  Often the number of recovery blocks is 5% or 10% of the number of input blocks. 

Next, we choose the code matrix.  The code matrix has a column for each input block and a row for each recovery block.  The elements of the matrix can be anything --- PAR 3.0 supports any systematic linear code.  Codes vary in speed and the probability of recoverying from an error.

Now, for each input vector, we make a recovery vector by multiplying the input vector with the code matrix.  There is only one code matrix; the code matrix is the same for each vector.  Since there is one recovery vector for each input vector, there are 1024 recovery vectors.  The length of the recovery vectors is determine by how many recovery blocks we want.  

The recovery vectors' data is then reorganized to make the recovery blocks.  The elements of the first vector make the first Galois-sized part of each recovery block.  In our example, the Galois Field size is 2 bytes, so the first recovery vector's elements make the first 2 bytes of each recovery block.  The elements of the second recovery vector make the 3rd and 4th bytes of each recovery block.  Etc.  There are 1024 recovery vectors, so each recovery block has 2*1024=2048 bytes.  This is the block size; recovery blocks are the same size as the input blocks.  

The recovery blocks are stored in a Par 3.0 file or multiple PAR 3.0 files.  The input blocks can be stored in their original files or put in Par 3.0 file(s).  The PAR 3.0 files contain a checksum for every input and recovery block.  After the files are stored or transmitted, the checksums are used to determine which blocks are damaged.

If there are any input blocks missing or damaged, we need to do recovery.  First, we identify elements of the input vectors associated with the missing/damaged input blocks.  Next, we identify elements of the recovery vectors associated with the missing/damaged recovery block.  We then perform the math (described above) which uses the good elements of each recovery vector to recover the bad elements of its associated input vector.  The math requires inverting a submatrix of the code matrix and, if the right inverse does not exist, we fail.  

After recovering the missing elements of each input vector, the data is reorganized to regenerate the missing input blocks.  Those blocks are written into their associated files, which should complete the repair.  Par 3.0 has a checksum for each file to make sure that the repair process worked correctly.


File Format Basics:

The PAR 3.0 file itself is made of packets - self-contained parts with their own checksum. This design prevents damage to one part of the file from making the whole file unusable. 

Packets have a type and each type of packet serves a different purpose.  One describes the matrix.  Another contains the checksums of input blocks.  Yet another contains a recovery block.  There are many other types.

A PAR 3.0 file is only required to contain 1 specific packet - the packet that identifies the client that created the file. This way, if clients are creating files that don't match the specification in some way, they can be tracked down.

The packets can be packaged into multiple files. Files can contain duplicate packets - in fact, this is recommended for vital packets, such as the ones that describe the input files. Packets can appear in any order in a file, but there is a recommended order if you want to support clients that recover the file(s) in a single pass.  



Conventions:

There are a number of conventions used in the design of this specification.

The data is 8-byte aligned. That is, every field starts on an index in the file which is congruent to zero, modulus 8. (That is, address % 8 == 0) This is because some memory systems function faster if 64-bit quantities are 8-byte aligned. It should be noted that a file could be corrupted (bytes inserted or deleted) to throw off the alignment. 

All integers in this version of the spec are unsigned integers of either 4 or 8 bytes in length.

Strings are not null-terminated. This is to prevent hackers from using stack-overflow attacks. In order to make a string 8-byte aligned, 1 to 7 zero bytes may be appended.  If an N-byte field contains an array, a null-terminated string can be created by copying the N-byte field into a character array of length N+1 and then the setting the N+1 character to '\0'.

The lengths of arrays and strings are often implicit. For example, if a region is known to be 32 bytes and that region contains an 8-byte integer and a string, then the string is known to take up 24 bytes. The string is then at least 17 bytes in length, since the 24 bytes contains 0 to 7 bytes of NUL padding at the end.

All strings are UTF-8.  Warning for OSX/MacOS clients: Unicode has multiple ways to encode the same string.  An e with an accent mark can be encoded as a single character (U+00e9) or two characters, one for the e (U+0065) and one for the accent mark (U+0301).  Par 3.0 does not require a particular encoding.  Forcing a particular encoding is called "normalization" in the Unicode vocabulary.  Most file systems do not normalize filenames and just treat the UTF-8 as a sequence of bytes.  Par 3.0 follows their practice.  However, HFS+ was Apple's default filesystem from 1998 to 2017 and it enforces normalizes.  Thus, if a Par client writes a UTF-8 filename, the HFS+ file system may change the filename.  Clients for OSX/MacOS should be aware of this possibility.  Apple's current default filesystem, APFS, does not do normalization.  

The lengths of files and parts of files are determined by 8-byte integers. This is to support OSes that can handle files longer than 4GB.

All integers are little endian. (This is the default on x86 and x86-64 CPUs.)

Par 3.0 uses multiple hash functions.  The "rolling hash" is CRC32C.  It is used to identify input blocks that are not in their expected location.  This hash is only 32 bits long and may not uniquely identify a block.  

For uniqueness, Par 3.0 uses the KangarooTwelve hash, a.k.a. K12 hash.  This is a longer hash with cryptographic properties.  The K12 hash of a block or file is assumed to be unique.

The recovery set is identified by a 16-byte value known as the Recovery Set ID. Every part of the PAR file that affects a recovery set contains the recovery set ID. In this 3.0 version, the Recovery Set ID is calculated as K12 hash of certain values.  The way of calculating this value could change in future versions; clients reading files should not rely on how it is calculated.

Files are identified by a "file index", which is an 8-byte unsigned integer.  If there are N files, they are assigned file indices of 0, 1, 2, ..., N-1.  The lowest file indices are assigned to files that have data to be protected.  Next comes data files that are not protected.  The highest indices go to files without any data, such as directories, hard links, symbolic links, etc..  

Every byte of a PAR file is specified. There are no places to throw junk bytes that can be any value. Padding, where needed, is specified to be zero bytes. The order of items in all arrays is specified.

Description:

A PAR 3.0 file consists of a sequence of "packets". A packet has a fixed sized header and a variable length body. The packet header contains a checksum for the packet - if the packet is damaged, the packet is ignored. The packet header also contains a packet-type. If the client does not understand the packet type, the packet is ignored. To be compliant with this specification, a client must understand the "core" set of packets. Client may process the optional packets or create their own application-specific packets.


Packet Header

Table: Packet Header
Length (bytes)	Type	Description
8	byte[8]	Magic sequence. Used to quickly identify location of packets. Value = {'P', 'A', 'R', '3', '\0', 'P', 'K', 'T'} (ASCII)
8	8-byte uint	Length of the entire packet. Must be multiple of 8. (NB: Includes length of header.)
16	K12 hash	K12 Hash of packet. Used as a checksum for the packet. Calculation starts at first byte of Recovery Set ID and ends at last byte of body. Does not include the magic sequence, length field or this field. !!!!!!!!---is the flowing true???????  NB: The MD5 Hash, by its definition, includes the length as if it were appended to the packet.
16	K12 hash	Recovery Set ID.  All packets that belong together have the same recovery set ID. (See !!!!!!!! for how it is calculated.)
16	byte[16]	Type. Can be anything. All beginning "PAR " (ASCII) are reserved for specification-defined packets. Application-specific packets are recommended to begin with the ASCII name of the client.
?*8	?	Body of Packet. Must be a multiple of 8 bytes.

There are various types of packets. The "core" set of packets - the set of packets that all clients must recognize and process - are listed next. For each, the value for the "type" field will be listed along with the contents of the body of the packet. 


Creator packet

This packet is used to identify the client that created the file. It is required to be in every PAR file. If a client is unable to process a recovery set, the contents of the creator packet must be shown to the user. The goal of this is that any client incompatibilities can be found and resolved quickly.

The creator packet has a type value of "PAR 2.0\0Creator\0" (ASCII). The packet's body contains the following:

Table: Creator Packet Body Contents
Length (bytes)	Type	Description
?*8	UTF-8 char array	UTF-8 text identifying the client. This should also include a way to contact the client's creator - either through a URL or an email address. NB: This is not a null terminated string!

It is recommended that the text in the creator packet include any parameters used to generate the file.  For example, the command line arguments.  This will aid in debugging problems.


Matrix packet

This packet sets the block size and Galois Field.

The creator packet has a type value of "PAR 3.0\0Matrix\0\0" (ASCII). The packet's body contains the following:

Table: Matrix Packet Body Contents
Length (bytes)	Type	Description
8	8-byte uint	The size of the Galois field in bytes.
?*8	?-byte GF	The generator of the Galois field.
8	8-byte uint	Number of Galois field elements in a block.

The block size is gotten by multiplying the size of the Galois field (in bytes) by the last field.  (Block size is encoded this way so that all unsigned integer values are valid.)

The generator is an element of the Galois field, written in little-endian format and padded with 0 to 7 zero bytes afterwards.  Thus, if the Galois field had a size of 2-bytes and a generator of 0x0001100B, the first two bytes would hold the generator in little-endian format and the next 6 bytes would be zeroes.

A client is not expected to support every Galois field.  It is required to support:

Table: Required Supported Galois Fields
Size (bits)    Generator (in binary)
8              0x11011B
16             0x1100B
128            0x10000111B

Note: The 8-bit Galois field is supported by the x86 instruction GF2P8MULB.

Note: The 16-bit Galois field is the same as in Par 2.0.

Note: A 64-bit Galois field is supported by the x86 instruction CLMUL.

Note: The 128-bit Galois field is implemented by Intel in this white paper:
https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/carry-less-multiplication-instruction-in-gcm-mode-paper.pdf

Note: The ARM processor has an instruction extension called "NEON" with a VMULL instruction.  VMULL.P8 will do eight 8-bit Galois field multiplications at once.  
During any recovery, there should be only 1 matrix packet.  (The same packet may be repeated multiple times.)


Matrix Rows packet

This packet describes some rows of the matrix.  It either contains the elements in those rows or describes how to compute them.

The creator packet has a type value of "PAR 3.0\0Rows\0\0\0\0" (ASCII). The packet's body contains the following:

Table: Matrix Rows Packet Body Contents
Length (bytes)	Type	Description
16	K12 hash	The checksum from the packet header of the matrix packet.
8	unsigned int	The generator of the Galois field.  Clients are only required to support values generator 0x0001100B. 
?*8	various	
?*8	UTF-8 char array	UTF-8 text identifying the client. This should also include a way to contact the client's creator - either through a URL or an email address. NB: This is not a null terminated string!

It is recommended that the text in the creator packet include any parameters used to generate the file.  For example, the command line arguments.  This will aid in debugging problems.




File hash  (license, code, projects using, speed, ...)
  Blake3 :
    8 times faster than MD5, using single thread SSE, 16kB input
       ---> Blake3 paper says it is roughly the same speed, maybe a touch faster, than KangarooTwelve
       ---> same paper says it is much faster on an ARM (Raspberry Pi)
       ---> VERY multi-threadable
    Public Domain CC0 1.0
    Rust is default implementation; C doesn't use threads.
    GCC or MSVC
    256-bit output
  KangarooTwelve:
    Mostly Public Domain CC0
    Python or Rust or C
{'fraction_non_alphanumeric': 0.0429961663226187, 'fraction_numerical': 0.016484812739604837, 'mean_word_length': 3.863186576796214, 'pattern_counts': {'":': 2, '<': 15, '<?xml version=': 0, '>': 21, 'https://': 1, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '518150', 'n_tokens_mistral': 8993, 'n_tokens_neox': 8277, 'n_words': 5651}