Re: [gentoo-user] hard drive encryption

[Florian Philipp]

Am 13.03.2012 20:07, schrieb Stroller:
>
> On 13 March 2012, at 18:18, Michael Mol wrote:
>> ...
>>> So I assume the i586 version is better for you --- unless GCC
>>> suddenly got a lot better at optimizing code.
>>
>> Since when, exactly? GCC isn't the best compiler at optimization,
>> but I fully expect current versions to produce better code for
>> x86-64 than hand-tuned i586. Wider registers, more registers,
>> crypto acceleration instructions and SIMD instructions are all very
>> nice to have. I don't know the specifics of AES, though, or what
>> kind of crypto algorithm it is, so it's entirely possible that one
>> can't effectively parallelize it except in some relatively unique
>> circumstances.
>
> Do you have much experience of writing assembler?
>
> I don't, and I'm not an expert on this, but I've read the odd blog
> article on this subject over the years.
>
> What I've read often has the programmer looking at the compiled gcc
> bytecode and examining what it does. The compiler might not care how
> many registers it uses, and thus a variable might find itself
> frequently swapped back into RAM; the programmer does not have any
> control over the compiler, and IIRC some flags reserve a register for
> degugging (IIRC -fomit-frame-pointer disables this). I think it's
> possible to use registers more efficiently by swapping them (??) or
> by using bitwise comparisons and other tricks.
>

You recall correctly about the frame pointer.

Concerning the register usage: I'm no expert in this field, either, but
I think the main issue is not simply register allocation but branch and
exception prediction and so on. The compiler can either optimize for a
seamless continuation if the jump happens or if it doesn't. A human or a
just-in-time compiler can better handle these cases by predicting the
outcome of -- in the case of a JIT -- analyze the outcome of the first
few iterations.

OT: IIRC, register reuse is also the main performance problem of
state-of-the-art javascript engines, at the moment. Concerning the code
they compile at runtime, they are nearly as good as `gcc -O0` but they
have the same problem concerning registers (GCC with -O0 produces code
that works exactly as you describe above: Storing the result after every
computation and loading it again).

> Assembler optimisation is only used on sections of code that are at
> the core of a loop - that are called hundreds or thousands (even
> millions?) of times during the program's execution. It's not for
> code, such as reading the .config file or initialisation, which is
> only called once. Because the code in the core of the loop is called
> so often, you don't have to achieve much of an optimisation for the
> aggregate to be much more considerable.
>
> The operations in question may only be constitute a few lines of C,
> or a handful of machine operations, so it boils down to an algorithm
> that a human programmer is capable of getting a grip on and
> comprehending. Whilst compilers are clearly more efficient for large
> programs, on this micro scale, humans are more clever and creative
> than machines.
>
> Encryption / decryption is an example of code that lends itself to
> this kind of optimisation. In particular AES was designed, I believe,
> to be amenable to implementation in this way. The reason for that was
> that it was desirable to have it run on embedded devices and on
> dedicated chips. So it boils down to a simple bitswap operation (??)
> - the plaintext is modified by the encryption key, input and output
> as a fast stream. Each byte goes in, each byte goes out, the same
> function performed on each one.
>

Well, sort of. First of, you are right, AES was designed with hardware
implementations in mind.

The algorithm boils down to a number of substitution and permutation
networks and XOR operations (I assume that's what you meant with byte
swap). If you look at the portable C code
(/usr/src/linux/crypto/aes_generic.c), you can see that it mostly
consists of lookup tables and XORs.

The thing about "each byte goes in, each byte goes out", however, is a
bit wrong. What you think of is a stream cipher like RC4. AES is a block
cipher. These use an (in this case 128 bit long) input string and XOR it
with the encryption (sub-)key and shuffle it around according to the
exact algorithm.

> Another operation that lends itself to assembler optimisation is
> video decoding - the video is encoded only once, and then may be
> played back hundreds or millions of times by different people. The
> same operations must be repeated a number of times on each frame,
> then c 25 - 60 frames are decoded per second, so at least 90,000
> frames per hour. Again, the smallest optimisation is worthwhile.
>
> Stroller.
>
>