Re: Re: infinint, libdar

(Sorry for that last mail, sent in error)

Thank you very much. Right now I have a couple other questions I've
encountered:

In the terminateur
------------------------------------------------------

Here's how I interpreted the terminator format:

Terminator format:

+---------------+..........+------------+------------+
|               |          |            |            |
|  Infinint     |  0x00    |  Bitfield  |  0xFF      |
|  Catalog Pos  |  Aligns  |  Term Cap  |  Term Cap  |
|               |          |            |            |
+---------------+..........+------------+------------+
 (A)             (B)        (C)          (D)

(2)---------------------->  <----------------------(1)
Read Order
   (1) - Terminator cap is read first, from EOF to bitfield
       - Cap is used to determine size of infinint, infinint offset
   (2) - Infinint is read from found offset. Infinint indicates
         offset of archive catalog


BLOCK_SIZE - Number of bytes in logical grouping. Currently 4 bytes.

Catalog Position Indicator
   (A) - Infinint containing the offset of the beginning of the catalog
   (B) - N 0x00 bytes. Aligns end of infinint to BLOCK_SIZE boundary

Terminator Cap (Indicates length of infinint
   (C) - 1 bitfield indicating from 0 to 7 additional blocks in
         excess of 8 block groups.

         bitfield format - 

        +-------------------------------+
        | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
        +---+---+---+---+---+---+---+---+
        | 1 | - | - | - | - | - | - | - |  1 extra blocks
        | 1 | 1 | - | - | - | - | - | - |  2 extra blocks
        | 1 | 1 | 1 | - | - | - | - | - |  3 extra blocks ...
        |   |   |   |   |   |   |   |   |
        | 1 | 1 | 1 | 1 | 1 | 1 | 1 | - |  7 extra blocks
        +-------------------------------+

   (D) - N 0xFF bytes. One byte for each group of 8 integers 



When implementing this, I had a concern. Usually, the last byte
in the file is 0xC0, indicating the infinint starts two blocks
before the beginning of the size string. But the code I wrote
(which I tried to match the to C++ code) does this:

// position file-pointer to EOF
stream.seekEOF();
			
// read backward until non 0xFF byte if found
// (counting number of 0xFF (full 8 block group)
// indicator bytes found
do {
	
	a = stream.readUnsignedByteBackward();

	if (a == 0xFF)
	offset++;
} while (a == 0xFF);
			
// at this point, non 0xFF byte is found,
// which means the excess bitfield is found???


offset *= 8; // convert offset from number of 8 block groups
             // to number of blocks

// we now consider the first non 0xFF byte of terminator string (backward reading)
// (this was found in the loop above)

// we will count the number of bits set in the (potential) bitfield

while (a != 0)
{
	if ( (a & 0x80) == 0 ) // bitfield format excludes non-zero bytes with no 0x80 bit set
		throw new StreamCorruptedException("Incorrect bitfield format"); // <-- this will partially cover for the concern detailed above
	
	offset++;
	a <<= 1;
	a = a & 0xFF; // mask down to char size	
}
// The above loop is basically assuming that the byte will be 0x00 if it's not the bitfield

offset *= BLOCK_SIZE; // convert offset from number of blocks to number of bytes

if (offset < 0)
	throw new SourceException("Signed int overflow"); // signed int overflow


// current file-pointer is now ready to read in the byte after (before, of lower address)
// the bitfield.


// skip to the beginning of infinint (which contains the address of the start of
// the catalog
stream.skipBackward(offset);



Using this code, I considered the following cases, where "|" indicates
what we know to be the end of the infinint and the beginning of the size
field:

A normal two integer backwards infinint offset
... ... | 0xC0
 - no 0xFF found, read backward one to find excess bitfield, which indicates two

... ... | 0xC0 0xFF
- one 0xFF found, read backward one to find the excess bitfield, which indicates two more

... ... | 0xFF
- one 0xFF found, read backward one to find the excess bitfield, WHICH IN THIS CASE WILL
  READ INTO THE ACTUALL INFININT, AND SCREW UP THE OFFSET

The way I see it, this could be fixed by always outputing an excess bitfield, which would be
set to 0x00 if the infinint takes up an even group of 8 integers. But I didn't see the code
to do something like this. Is this a bug, or am I just missing something?




In the archive level header
------------------------------------------------------

+---------+------+---------------+------+
| edition | algo | command line  | flag |
|         |      |               |      |
+---------+------+---------------+------+


- command line		This is obviously written as a C style string, but I am missing
			how it is used in dar itself. All the archives I generate just
			have "N/A" set in that field. (I admit, I've been studying the
			libdar code it detail, but haven't touched the dar stuff yet).

- EA flag		SAVED_EA_ROOT = 0x80		how is this option used in dar?
			SAVED_EA_USER = 0x40		how is this option used in dar?

			SCRAMBLED = 0x20
			With this, I was thinking of adding gpg encryption and maybe other
			formats to my implementation. Any thoughts on changing this to
			match the algo format in dar edition 04 so different encryption
			schemes could be used? ;)


Again, thanks for helping me out with this. Basically, I'm attempting to put together the
peices for a real linux backup program (you know, background libraries, stuff like that), and
at first I was just going to pipe stuff to tar and rar and whatever else seemed good. But 
dar caught my eye, and I got really interested in the file format itself.

I actually had a big long conversation with a friend the other day about why the catalog has to
be stored at the end of the archive. I was the fact that dar archives can't really be read to or
written to pure one way pipes like tar archives can (they can, right?). But then I was thinking that
it doesn't seem like such a big deal since the whole idea of dar is that it would be written to
random access mediums in the first place, so why not take advantage of that, right?


Thanks,
Wesley Leggette




On Thu, 2004-04-29 at 15:14, Denis Corbin wrote:
> I thought I had replied to this mail, but cannot find my answer in the 
> mailing-list archive, so if I didn't replied sorry to reply so late !
> 
> The infinint when saved in file (in archive) are a variable byte field 
> representing the integer in network byte order. To determine how much 
> byte it has of length, this field is preceded by a header of variable 
> length, which is called "preamble" in the comments of the code (see 
> real_infinint.cpp and the infinint::dump() method for details).
> 
> This preamble contains only one bit set to one. This bit is located in 
> the last byte of the preamble. So while we read 0x00 the preamble is not 
> finished, when we reach a non null byte, this is the end of the header, 
> and this byte must have only one bit set to one. If we count the number 
> of bit  (not byte) that have been read and which are set to zero before 
> this bit set to 1, we get the size of the infinint field that follows 
> the preamble in TG unit. A TG is actually fixed to 4 byte.
> 
> I don't remember well where from I took "TG" for, G for Group, and T 
> maybe for Tributary ? TG = Tributary Group ? OK It was quite three years 
> ago (July 2001), and I had not to fix any bug in this part since that 
> time ! By the way, there is room to have the preamble of infinint 
> changed its structure, by giving a first byte containing two or more 
> bits set to one... actual code detects this condition and consider this 
> is a format it does not know, or a data corruption.
> 
> Let's take an example, in memory we have an infinint of 5 bytes (0x 
> FA.79.00.12.34, in network order), so we need two TG, to store it, (8 
> bytes), the preamble is then 0x40 (it would have been 0x80 for 1 TG, or 
>   0x00.80 for 9 TG (for a 36 bytes integer!) for example) We must add 
> tree bytes of padding to have the integer field be exactly 2 TG (=8 
> bytes) and not 5 bytes only, as it is in memory. So the resulting string 
> written in file is:
> 
> 0x40.00.00.00.FA.79.00.12.34
> ----+--------+--------------+
> Pre.| Padding| integer field|
> ----+-----------+-----------+
> Pre.|    1 TG   |   1 TG    |
> 
> the dot '.' in this notation separate each byte.
> 
> Wesley Leggette wrote:
> > In libdar, it's my impression that infinint's are dumped like this:
> > 
> > 0x00 + bit pattern - header indicating how long the infinint is
> > byte fields - actual data in network byte order
> > 
> > I'm having a hard time trying to figure out how exactly the header is
> > formed.
> > 
> > As a school project, I'm working on implementing a dar library in java,
> > hence the above question.
> > 
> > Also, I'd like to be able to use individual parts of libdar (to compare
> > libdar output with what I write in java). Is it best to set up a
> > generic_file and then call various dump() functions, or is there an
> > easier way?
> > 
> > 
> > 
> > -------------------------------------------------------
> > This SF.Net email is sponsored by: IBM Linux Tutorials
> > Free Linux tutorial presented by Daniel Robbins, President and CEO of
> > GenToo technologies. Learn everything from fundamentals to system
> > administration.http://ads.osdn.com/?ad_id=1470&alloc_id=3638&op=click
> 
> 
> 
> 
> -------------------------------------------------------
> This SF.Net email is sponsored by: Oracle 10g
> Get certified on the hottest thing ever to hit the market... Oracle 10g. 
> Take an Oracle 10g class now, and we'll give you the exam FREE. 
> http://ads.osdn.com/?ad_id=3149&alloc_id=8166&op=click
> _______________________________________________
> Dar-discussions mailing list
> Dar-discussions-5NWGOfrQmneRv+LV9MX5uipxlwaOVQ5f@public.gmane.org
> https://lists.sourceforge.net/lists/listinfo/dar-discussions



-------------------------------------------------------
This SF.Net email is sponsored by: Oracle 10g
Get certified on the hottest thing ever to hit the market... Oracle 10g. 
Take an Oracle 10g class now, and we'll give you the exam FREE. 
http://ads.osdn.com/?ad_id=3149&alloc_id=8166&op=click