[curves] Distribution-ready optimized code

[Irene Knapp]

Hi - guess I'll weigh in; I've been lurking here to learn more about
crypto, but my expertise is in language design.

Surely, what you are describing is a lightweight tool that either generates
LLVM bitcode, or hooks into the LLVM backends at a slightly lower level
than that to output particular instructions when that's what you really,
really want - but I suspect its hinting system already makes that
unnecessary for this use-case.  LLVM bitcode is precisely this "mostly
concrete assembly" concept that you're describing.

There's unfortunately no textual syntax for it.  So, I feel like what you
want is a straightforward C++ program that links against LLVM and consists
almost entirely of a long list of calls to "append this opcode" methods.

You'd want to set up your makefile or other build system to compile this
program, run it, and the program would be written to generate a native .o,
which the makefile would then link into the rest of the project as if it
had just come from a conventional compiler.

Irene

On Fri, Apr 3, 2015 at 11:11 AM Irene Knapp <ireneista at gmail.com> wrote:

> Hi - guess I'll weigh in; I've been lurking here to learn more about
> crypto, but my expertise is in language design.
>
> Surely, what you are describing is a lightweight tool that either
> generates LLVM bitcode, or hooks into the LLVM backends at a slightly lower
> level than that to output particular instructions when that's what you
> really, really want - but I suspect its hinting system already makes that
> unnecessary for this use-case.  LLVM bitcode is precisely this "mostly
> concrete assembly" concept that you're describing.
>
> There's unfortunately no textual syntax for it.  So, I feel like what you
> want is a straightforward C++ program that links against LLVM and consists
> almost entirely of a long list of calls to "append this opcode" methods.
>
> You'd want to set up your makefile or other build system to compile this
> program, run it, and the program would be written to generate a native .o,
> which the makefile would then link into the rest of the project as if it
> had just come from a conventional compiler.
>
> Irene
>
> On Fri, Apr 3, 2015 at 4:03 AM Andrew Moon <liquidsun at gmail.com> wrote:
>
>> OpenSSL's idea is interesting, but is a fairly horrible
>> implementation. The 32 bit x86 stuff uses a 'psuedo' language by
>> abusing perl while everything else (arm, x86-64, etc) is just parsing
>> raw asm, and everything has random kludges for specific instructions.
>> There's also no way to import/convert existing asm to their weird
>> pseudo-x86 format, and the C compiler (as well as the perl script!)
>> has no (easy) way to tell if the assembler even supports the
>> instruction set(s) being compiled.
>>
>> I don't really like the "programmable assembler assembler" code being
>> distributed as the sole file either, especially when it's trying to
>> re-use bits of code while generating for multiple instruction sets
>> (like OpenSSL does). It's difficult/impossible to tell what it is
>> doing without seeing the generated output, and trying to fix an issue
>> affecting one instruction set without stepping on the others would be
>> error-prone.
>>
>> Ideally, I think I'd want two different steps: An easy to use
>> "programmable assembler assembler" which handles boring stuff like
>> register allocation, stack allocation, instruction set validation,
>> constant data, stream interleaving (ARM), maybe a cycle/pipeline
>> analyzer such as http://pulsar.webshaker.net/ccc/ if I got greedy. I
>> guess I'm mostly describing PeachPy, but parsing some kind of source
>> file instead of the nasty python code; something that makes writing
>> the exact instructions you want as painless/efficient as possible.
>> Step 1 could also produce the annotations needed for verification
>> (automatically generated based on instructions and/or hand annotated),
>> metadata for Step 2 like # of arguments, xmm registers used for Win64,
>> etc.
>>
>> Step 2 is what you would need to include in any project using the
>> intermediate files, something to take the output from the first step
>> and perform all the necessary platform specific stuff that is only
>> known at compile time - ABI conversion, formatting for the assembler
>> code if needed, proper keywords/metadata for the output format. Maybe
>> just a static set of macros that are selected with ifdefs based on
>> what ./configure finds, maybe a separate program/script which creates
>> the final assembler file to compile.
>>
>> You'd then have the option of
>>
>> 1. Distribute the intermediate file and use Step 2 to build
>> 2. Distribute the source and the intermediate and use Step 2 to build, or
>> 3. Distribute the source and use both Step 1 & 2 to build
>>
>> On Tue, Mar 31, 2015 at 8:51 PM, Trevor Perrin <trevp at trevp.net> wrote:
>> > On Thu, Mar 19, 2015 at 11:36 AM, Samuel Neves <sneves at dei.uc.pt>
>> wrote:
>> >> On 03/19/2015 05:03 PM, Watson Ladd wrote:
>> >>> What about mixed 1 and 4? Distribute asm a tool made.
>> >>
>> >> This has the same problem as 1: you don't simply distribute one
>> assembly dump, you have to distribute one for each
>> >> toolchain/ABI/etc combo.
>> > [...]
>> >>
>> >> It's not really a major problem, but it is annoying enough that I
>> would very much prefer if the tool came with the
>> >> distribution. For that to happen, the tool must be portable, polished,
>> etc. OpenSSL went with Perl, but I would prefer
>> >> something better.
>> >
>> >
>> > So the OpenSSL approach is to emit asm from scripts.  This allows
>> > syntactic sugar (e.g. variable names for stack locations, loop
>> > unrolling).  There's also support for translating to different
>> > toolchain / ABI formats (e.g. it can convert AT&T syntax to Intel).
>> >
>> > It seems like you're okay with this approach but want a higher-quality
>> > tool that could be reused outside OpenSSL? (so asm source could be
>> > written in "perlasm" or similar and be ingested by different
>> > projects)?
>> >
>> > This makes sense but I wonder if having the source file be a
>> > string-processing script loses the ability to have code auditors or
>> > formal-methods tools validate the code at a higher level?
>> >
>> > I don't know that anyone's doing much formal validation of ECC
>> > codebases yet, but it seems like a potential good idea.  If the input
>> > source is a Perl script any formal validation tools would need to
>> > understand Perl (not likely) or would need to understand asm, and be
>> > re-run on every output flavor...
>> >
>> >
>> > Trevor
>> > _______________________________________________
>> > Curves mailing list
>> > Curves at moderncrypto.org
>> > https://moderncrypto.org/mailman/listinfo/curves
>> _______________________________________________
>> Curves mailing list
>> Curves at moderncrypto.org
>> https://moderncrypto.org/mailman/listinfo/curves
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150403/2f99722c/attachment.html>