linux-kernel - Re: [PATCH 03/10] AXFS: axfs.h

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Fri, 22 Aug 2008 14:04:12 +0200 (CEST)
From:	Geert Uytterhoeven <Geert.Uytterhoeven@...ycom.com>
To:	Arnd Bergmann <arnd@...db.de>
cc:	Jared Hulbert <jaredeh@...il.com>, Linux-kernel@...r.kernel.org,
	linux-embedded@...r.kernel.org,
	linux-mtd <linux-mtd@...ts.infradead.org>,
	Jörn Engel <joern@...fs.org>,
	tim.bird@...sony.com, cotte@...ibm.com, nickpiggin@...oo.com.au
Subject: Re: [PATCH 03/10] AXFS: axfs.h

On Fri, 22 Aug 2008, Arnd Bergmann wrote:
> On Friday 22 August 2008, Jared Hulbert wrote:
> > If I have an array of u64 numbers tracking small numbers (a[0] = 1;
> > a[1] = 2;) just throwing that onmedia is a big waste.
> > (0x0000000000000001; 0x0000000000000002)  Having different array types
> > for different images such as arrays of u8,u16,u32,u64 becomes less
> > efficient for 3,5,6 and 7 byte numbers, 3 bytes was a particularly
> > interesting size for me.
> > 
> > All I'm doing is removing the totally unnecessary zeros and aligning by bytes.
> > Take an array of u64 like this :
> > 0x0000000000000005
> > 0x0000000000001001
> > 0x00000000000a0000
> > 
> > I strip off the unneeded leading zeros:
> > 0x000005
> > 0x001001
> > 0x0a0000
> > 
> > Then pack them to byte alignment:
> > 0x0000050010010a0000
> > 
> > Sure it could be encoded more but that would make it harder to extract
> > the data.  This way I can read the data in one, maybe two, cache
> > misses.  A couple of shifts to deal with the alignment and endianness
> > and we are done.
> 
> So do I understand right that 3 bytes is your minimum size, and going
> smaller than that would not be helpful? Otherwise I would assume that
> storing a '5' should only take one byte instead of three.

>From the paper, the minimum size (called `depth') is 1.

> I don't unsterstand yet why you store the length of each word separate
> from the word. Most variable-length codes store that implicitly in
> the data itself, e.g. in the upper three bits, so that for storing
> 0x5, 0x1001, 0xa0000, this could e.g. end up as 0x054010014a0000,
> which is shorter than what you have, but not harder to decode.

AFAIU, the length (`depth') of each word is not stored separate, as the
depth is the same for all values in the same table.

With kind regards,

Geert Uytterhoeven
Software Architect

Sony Techsoft Centre Europe
The Corporate Village · Da Vincilaan 7-D1 · B-1935 Zaventem · Belgium

Phone:    +32 (0)2 700 8453
Fax:      +32 (0)2 700 8622
E-mail:   Geert.Uytterhoeven@...ycom.com
Internet: http://www.sony-europe.com/

A division of Sony Europe (Belgium) N.V.
VAT BE 0413.825.160 · RPR Brussels
Fortis · BIC GEBABEBB · IBAN BE41293037680010