-------------

Sunday, April 8, 2012

File Format rar

------------------------------------------------------------------------------------------

                         FILE FORMAT
         A file format is a particular way that information is encoded for storage in a computer file. Any list of file formats would contain both proprietary and open source. Since a disk drive, or indeed any computer storage, can store only bits, the computer must have some way of converting information to 0s and 1s and vice-versa. There are different kinds of formats for different kinds of information. Within any format type, e.g., word processor documents, there will typically be several different formats. Sometimes these formats competye with each other. File formats can be divided into proprietary and open formats.
 In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of that type can be stored. Data types are used within type systems, which offer various ways of defining, implementing and using them. Different type systems ensure varying degrees of type safety. Formally, a type can be defined as "any property of a programme we can determine without executing the program"
  Some file formats are designed for very particular sorts of data: PNG files, for example, store bitmapped images using lossless data compression. Other file formats, however, are designed for storage of several different types of data: the Ogg format can act as a container for many different types of multimedia, including any combination of audio and/or video, with or without text (such as subtitles), and metadata. A text file can contain any stream of characters, encoded for example as ASCII or Unicode, including possible control characters. Some file formats, such as HTML, Scalable Vector Graphics, and the source code of computer software are also text files with defined syntaxes that allow them to be used for specific purposes.

Overview
Almost all programming languages explicitly include the notion of data type, though different languages may use different terminology. Common data types may include:
  • integers,
  • booleans,
  • characters,
  • floating-point numbers,
  • alphanumeric strings.
For example, in the Java programming language, the "int" type represents the set of 32-bit integers ranging in value from -2,147,483,648 to 2,147,483,647, as well as the operations that can be performed on integers, such as addition, subtraction, and multiplication. Colors, on the other hand, are represented by three bytes denoting the amounts each of red, green, and blue, and one string representing that color's name; allowable operations include addition and subtraction, but not multiplication.
Most programming languages also allow the programmer to define additional data types, usually by combining multiple elements of other types and defining the valid operations of the new data type. For example, a programmer might create a new data type named "complex number" that would include real and imaginary parts. A data type also represents a constraint placed upon the interpretation of data in a type system, describing representation, interpretation and structure of values or objects stored in computer memory. The type system uses data type information to check correctness of computer programs that access or manipulate the data.

Classes of data types
Machine data types
All data in computers based on digital electronics is represented as bits (alternatives 0 and 1) on the lowest level. The smallest addressable unit of data is usually a group of bits called a byte (usually an octet, which is 8 bits). The unit processed by machine code instructions is called a word (as of 2011, typically 32 or 64 bits). Most instructions interpret the word as a binary number, such that a 32-bit word can represent unsigned integer values from 0 to 2^{32}-1 or signed integer values from -2^{31} to 2^{31}-1. Because of two's complement, the machine language and machine doesn't need to distinguish between these unsigned and signed data types for the most part.
There is a specific set of arithmetic instructions that use a different interpretation of the bits in word as a floating-point number.
Machine data types need to be exposed or made available in systems or low-level programming languages, allowing fine-grained control over hardware. The C programming language, for instance, supplies integer types of various widths, such as short and long. If a corresponding native type does not exist on the target platform, the compiler will break them down into code using types that do exist. For instance, if a 32-bit integer is requested on a 16 bit platform, the compiler will tacitly treat it as an array of two 16 bit integers.
Several languages allow binary and hexadecimal literals, for convenient manipulation of machine data.
In higher level programming, machine data types are often hidden or abstracted as an implementation detail that would render code less portable if exposed. For instance, a generic numeric type might be supplied instead of integers of some specific bit-width.
The boolean type
The Boolean type represents the values: true and false. Although only two values are possible, they are rarely implemented as a single binary digit for efficiency reasons. Many programming languages do not have an explicit boolean type, instead interpreting (for instance) 0 as false and other values as true.
Numeric types
Such as:
  • The integer data types, or "whole numbers". May be subtyped according to their ability to contain negative values (eg. unsigned in C and C++). May also have a small number of predefined subtypes (such as short and long in C/C++); or allow users to freely define subranges such as 1..12 (eg. Pascal/Ada).
  • Floating point data types, sometimes misleadingly called reals, contain fractional values. They usually have predefined limits on both their maximum values and their precision.
  • Fixed point data types are convenient for representing monetary values. They are often implemented internally as integers, leading to predefined limits.
  • Bignum or arbitrary precision numeric types lack predefined limits. They are not primitive types, and are used sparingly for efficiency reasons.
String and text types
Such as
  • Alphanumeric character. A letter of the alphabet, digit, blank space, punctuation mark, etc.
  • Alphanumeric strings, a sequence of characters. They are typically used to represent words and text.
Character and string types can store sequences of characters from a character set such as ASCII. Since most character sets include the digits, it is possible to have a numeric string, such as"1234". However, many languages would still treat these as belonging to a different type to the numeric value 1234.
Character and string types can have different subtypes according to the required character "width". The original 7-bit wide ASCII was found to be limited, and superseded by 8 and 16-bit sets, which can encode a wide variety of non-latin alphabets (Hebrew, Chinese) and other symbols. Strings may be either stretch-to-fit or of fixed size, even in the same programming language. They may also be subtyped by their maximum size.
Note: strings are not primitive in all languages, for instance C: they may be composed from arrays of characters.
Type systems
A type system associates types with each computed value. By examining the flow of these values, a type system attempts to prove that no type errors can occur. The type system in question determines what constitutes a type error, but a type system generally seeks to guarantee that operations expecting a certain kind of value are not used with values for which that operation does not make sense.
A compiler may use the static type of a value to optimize the storage it needs and the choice of algorithms for operations on the value. In many C compilers the float data type, for example, is represented in 32 bits, in accord with the IEEE specification for single-precision floating point numbers. They will thus use floating-point-specific microprocessor operations on those values (floating-point addition, multiplication, etc.).
The depth of type constraints and the manner of their evaluation affect the typing of the language. A programming language may further associate an operation with varying concrete algorithms on each type in the case of type polymorphism. Type theory is the study of type systems, although the concrete type systems of programming languages originate from practical issues of computer architecture, compiler implementation, and language design.
Type systems may be variously static or dynamic, strong or weak typing, and so forth.

The RAR Format
1 Introduction
This document, a work-in-progress, describes the RAR format. It serves a similar role that the ZIP App Note does for the ZIP format.
NOTE 1: This documentation MUST NOT be used to create RAR-compatible archive programs like WinRAR. It is only for the purposes of writing decompression software (i.e. unrar) in various languages. It was reverse-engineered from the UnRAR source located at this page with Eugene Roshal's permission.
NOTE 2: This documentation will initially focus on what I believe is Version 3 of the RAR format.
1.1 License
2 General Format of a .RAR File
Overall .RAR file format:
signature               7 bytes    (0x52 0x61 0x72 0x21 0x1A 0x0
7 0x00)
[1st volume header]
...
[2nd volume header]
...
...
[nth volume header]
...
In general, a modern single-volume RAR file has MAIN_HEAD structure followed by multiple FILE_HEAD structures.
2.1 Volume Header Format
The Base Header Block is:
header_crc              2 bytes
header_type             1 byte
header_flags            2 bytes
header_size             2 bytes
The header_size indicates how many total bytes the header requires. The header_type field determines how the remaining bytes should be interpreted.
2.1.1 Header Type
The header type is 8 bits (1 byte) and can have the following values:
Value
Type
0x72
MARK_HEAD
0x73
MAIN_HEAD
0x74
FILE_HEAD
0x75
COMM_HEAD
0x76
AV_HEAD
0x77
SUB_HEAD
0x78
PROTECT_HEAD
0x79
SIGN_HEAD
0x7a
NEWSUB_HEAD
0x7b
ENDARC_HEAD
2.1.1.1 MARK_HEAD
TBD

2.1.1.2 MAIN_HEAD
The remaining bytes in the volume header for MAIN_HEAD are:
HighPosAv               2 bytes
PosAV                   4 bytes
EncryptVer              1 byte (only present if MHD_ENCRYPTVER 
is set)
2.1.1.3 FILE_HEAD
The remaining bytes in the FILE_HEAD structure are:
PackSize                4 bytes
UnpSize                 4 bytes
HostOS                  1 byte
FileCRC                 4 bytes
FileTime                4 bytes
UnpVer                  1 byte
Method                  1 byte
NameSize                2 bytes
FileAttr                4 bytes
HighPackSize            4 bytes (only present if LHD_LARGE is
 set)
HighUnpSize             4 bytes (only present if LHD_LARGE is
 set)
FileName                (NameSize) bytes
Salt                    8 bytes (only present if LHD_SALT is set)
ExtTime Structure       See Description (only present if LHD_
EXTTIME is set)
Packed Data             (Total Packed Size) bytes
If the LHD_LARGE flag is set, then the archive is large and 64-bits are needed to represent the packed and unpacked size. HighPackSize is used as the upper 32-bits and PackSize is used as the lower 32-bits for the packed size in bytes. HighUnpSize is used as the upper 32-bits and UnpSize is used as the lower 32-bits for the unpacked size in bytes.
ExtTime Structure
Follow the following pseudo-code to read in the ExtTime Structure.
TODO: Fill in details of what this structure represents.
var extTimeFlags = readBits(16)

mtime:
mtime_rmode = extTimeFlags >> 12
if ((mtime_rmode & 8)==0) goto ctime
mtime_count = mtime_rmode & 0x3
mtime_reminder = readBits(8*mtime_count);

ctime:
ctime_rmode = extTimeFlags >> 8
if ((ctime_rmode & 8)==0) goto atime
Set ctime to readBits(16)
ctime_count = ctime_rmode & 0x3
ctime_reminder = readBits(8*ctime_count)

atime:
atime_rmode = extTimeFlags >> 4
if ((atime_rmode & 8)==0) goto arctime
Set atime to readBits(16)
atime_count = atime_rmode & 0x3
atime_reminder = readBits(8*atime_count)

arctime:
arctime_rmode = extTimeFlags
if ((arctime_rmode & 8)==0) goto done_exttime
Set arctime to readBits(16)
arctime_count = arctime_rmode & 0x3
arctime_reminder = readBits(8*arctime_count)

done_exttime
2.1.1.4 COMM_HEAD TBD
2.1.1.5 AV_HEAD TBD
2.1.1.6 SUB_HEAD TBD
2.1.1.7 PROTECT_HEAD TBD
2.1.1.8 SIGN_HEAD TBD
2.1.1.9 NEWSUB_HEAD TBD
2.1.1.10 ENDARC_HEAD TBD

2.1.2 Header Flags
The header flags are 16 bits (2 bytes). Depending on the type of Volume Header, the flags are interpreted differently.
The Main Header Flags are:
Value
Flag
0x0001
MHD_VOLUME
0x0002
MHD_COMMENT
0x0004
MHD_LOCK
0x0008
MHD_SOLID
0x0010
MHD_PACK_COMMENT or MHD_NEWNUMBERING
0x0020
MHD_AV
0x0040
MHD_PROTECT
0x0080
MHD_PASSWORD
0x0100
MHD_FIRSTVOLUME
0x0200
MHD_ENCRYPTVER
The File Header Flags are:
Value
Flag
0x0001
LHD_SPLIT_BEFORE
0x0002
LHD_SPLIT_AFTER
0x0004
LHD_PASSWORD
0x0008
LHD_COMMENT
0x0010
LHD_SOLID
0x0100
LHD_LARGE
0x0200
LHD_UNICODE
0x0400
LHD_SALT
0x0800
LHD_VERSION
0x1000
LHD_EXTTIME
0x2000
LHD_EXTFLAGS

2.1.2.1 MHD_VOLUME Value 0x0001. TBD
2.1.2.2 MHD_COMMENT Value 0x0002. TBD
2.1.2.3 MHD_LOCK Value 0x0004. TBD
2.1.2.4 MHD_SOLID Value 0x0008. TBD
2.1.2.5 MHD_PACK_COMMENT Value 0x0010. TBD
2.1.2.6 MHD_AV Value 0x0020. TBD
2.1.2.7 MHD_PROTECT Value 0x0040. TBD
2.1.2.8 MHD_PASSWORD Value 0x0080. TBD
2.1.2.9 MHD_FIRSTVOLUME Value 0x0100. TBD
2.1.2.10 MHD_ENCRYPTVER
Value 0x0200. Indicates whether encryption is present in the archive volume.

2.1.2.11 LHD_SPLIT_BEFORE Value 0x0001. TBD
2.1.2.12 LHD_SPLIT_AFTER Value 0x0002. TBD
2.1.2.13 LHD_PASSWORD Value 0x0004. TBD
2.1.2.14 LHD_COMMENT Value 0x0008. TBD
2.1.2.15 LHD_SOLID Value 0x0010. TBD
2.1.2.16 LHD_LARGE Value 0x0100. Indicates if the archive is large. In this case, 64 bits are used to describe the packed          and unpacked size.
2.1.2.17 LHD_UNICODE Value 0x0200. Indicates if the filename is Unicode.
2.1.2.18 LHD_SALT Value 0x0400. Indicates if the 64-bit salt value is present.
2.1.2.19 LHD_VERSION Value 0x0800. TBD

2.1.2.20 LHD_EXTTIME Value 0x1000. The ExtTime Structure is
present in the FILE_HEAD header.
2.1.2.21 LHD_EXTFLAGS Value 0x2000. TBD
3 Unpacking
Once the header information and packed bytes have been extracted, the packed bytes must then be unpacked. RAR uses a variety of algorithms for this. Chief among these are Lempel-Ziv compression and Prediction by Partial Matching. The details of the unpacking are specified in the following subsections based on the values of UnpVer and Method as decoded in the FILE_HEAD structure.
If Method is 0x30 (decimal 48), then the packed bytes are the unpacked bytes and no decompression/unpacking is necessary (i.e. the file was not compressed).

Otherwise:
UnpVer Value (decimal)
Algorithm To Use
15
Unpack15
20
Unpack20
26
29
Unpack29
36
3.1 Unpack15 TBD
3.2 Unpack20 TBD
3.3 Unpack29 The structure of packed data consists of N number of blocks. If    the first bit of a block is set, then process the block as a PPM block. Otherwise, this is an LZ block.
3.3.1 LZ Block
The format of a LZ block is:
isPPM                   1 bit
keepOldTable            1 bit
huffmanCodeTable        (variable size)
3.3.1.1 Huffman Code Tables
The Huffman Encoding tables consist a series of bit lengths. For a more thorough treatment of the concepts of Huffman Encoding, see the Deflate spec. The RAR format uses a set of twenty bit lengths to construct Huffman Codes. The Huffman Encoding tables in RAR files consist of at most twenty entries of the format:
BitLength               4 bits
ZeroCount               4 bits (only present if BitLength is 15)
If BitLength is 15, then the next 4 bits are read as ZeroCount. If the ZeroCount is 0, then the bit length is 15, otherwise (ZeroCount+2) is the number of consecutive zero bit lengths that are in the table. For instance, if the following 4-bit numbers are present:
0x8
indicates a bit-length of 8
0x4
indicates a bit-length of 4
0x4
indicates a bit-length of 4
0x2
indicates a bit-length of 2
0xF
these two 4-bit numbers specify a bit-length of 15
0x0
0xF
these two 4-bit numbers specify a run of 5 zeros
0x3
0x9
indicates a bit-length of 9
0x3
indicates a bit-length of 3
0xF
these two 4-bit numbers specify a run of 8 zeros
0x6
This example describes a Huffman Encoding Bit Length table of:
Code
Bit Length
Code
BitLength
1
8
11
9
2
4
12
3
3
4
13
0
4
2
14
0
5
15
15
0
6
0
16
0
7
0
17
0
8
0
18
0
9
0
19
0
10
0
20
0
Once the twenty bit lengths are obtained, the Huffman Encoding table is constructed by using the following algorithm:
1) Count the number of codes for each code length.  Let
   LenCount[N] be the number of codes of length N, where
 N = {1..16}.
            
2) Find the decode length and positions:

        N = 0
        TmpPos[0] = 0
        DecodePos[0] = 0
        DecodeLen[0] = 0
        for (I = 1; I < 16; I++)
        {
            N = 2 * (N+LenCount[I])
            M = N << (15-I)
            if (M > 0xFFFF) M = 0xFFFF
           
            DecodeLen[I] = (unsigned int)M
            TmpPos[I] = DecodePos[I] = DecodePos[I-1] + 
LenCount[I-1]
        }

3) Assign numerical values to all codes:

        for (I = 0; I < TableSize; I++)
        {
            if (BitLength[I] != 0)
                DecodeNum[ TmpPos[BitLength[I] & 0xF]++ ] = I
        }
READ MORE - File Format rar --------------------------------------------------