Maybe I didn't express myself clearly. I knew loading stuff word by word would be much faster, thanks to my knowledge of the memory hierarchy, caching, and pipelining.
What I didn't expect was the magnitude of the overall impact. The core round functions are much, much faster that I had anticipated. I didn't think the loading code, even in its slow version, would account for a significant percentage of the total running time.
> It would be great if this was written in another language.
Easier said than done. I aim for easy integration in projects written in basically anything: C, C++, OCaml, Rust, Python… What would you suggest? Rust? That's a possibility, but (i) it's LLVM only at the moment, and (ii) I believe there's an impedance mismatch between Rust and a C compatible ABI.
I would totally recommend to rewrite the whole thing in Rust for Rust projects, though.
If you're curious, check this out: https://doc.rust-lang.org/1.5.0/book/ffi.html
> I would totally recommend to rewrite the whole thing in Rust for Rust projects, though.
Any time you rewrite anything, you run the risk of introducing new and unexpected bugs, and you're just doing unnecessary, complex work fraught with pitfalls (doubly so here) -- generally a Rust project would create a wrapper around the C code, invoke the methods and expose idiomatic APIs on top to avoid just that.
This is my go-to article on re-writing things and why not to: https://www.joelonsoftware.com/2000/04/06/things-you-should-...
To be clear I'm not saying you made a mis-step, just that your arguments for it don't seem at first glance to support your decision.
I was just telling one has to write a wrapper either way. Idiomatic Rust is not idiomatic C, so you would need to have a "C ABI" interface in addition to the clean Rust interface.
> That it's LLVM only appears to me irrelevant […]
Not if it targets less platforms than GCC. Though that will likely matter less and less in the future.
> So long as you get rustc up and running, what does it matter it's architecture?
You have to get it up and running. You have another build step. You have to use a binary library (can't just include the source code). It's not much, but I want to maximise ease of deployment.
Portability does not equal 'without blemishes'. It simply means that when compiled across platforms it will perform as expected.
But from a rather philosophical point of view, C is basically Portability 1.0, it was one of the first truly portable "fast" languages. I'd like to think that we could do better than C with 40 years or CS research and industry experience.
Of course, there's the whole second-system syndrome so it's a wicked problem :)
Yeah, you don't even need a new, hip language to avoid C's pitfalls.
> Portability does not equal 'without blemishes'. It simply means that when compiled across platforms it will perform as expected.
By that measure, C is not portable, since it will behave differently across multiple platforms – or multiple compilers, multiple compiler versions, even multiple optimization settings.
So.. it's portable, then?
C is meant to map easily to a wide range of hardware without overhead, conceptually it's almost the opposite of portability since it precludes creating standard abstractions that would hold true across architectures as those could not map to native functionality across the board.
It's easy to compile C programs on a different architecture however, which is probably where this argument stems from. Remember when we switched from 32 to 64bits? How many codebases managed to make the jump painlessly?
The problem is that it returns an "int" which contains a negative value on errors and the number of character written on success.
Of course that means that it's possible to write a string whose size doesn't fit in an int.
For instance if you have a 64bit computer (and enough RAM) you can try the following code:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
int main(void) {
size_t len = 0x80000001UL;
char *str = malloc(len);
assert(str);
memset(str, 'a', len);
str[len - 1] = '\0';
fprintf(stderr, "\n%d\n", printf(str));
return 0;
}
On my computer the "printf" manages to print the whole string successfully but it returns... -1, signaling an error.
The size shouldn't be returned that way, it should be a "size_t" as an output parameter (since you also need a special value for errors). In Rust you'd use "Result<usize>" and you'd have a more elegant solution. Of course you can't really do that in C (except by returning a struct, which is a bit cumbersome) so I guess they said "meh, who prints that much text anyway?" and assumed an int would be good enough.
C provided "at least N bits" guarantees for its integer types since its first standard (for the curious: char at least 8-bit, short at least 16-bit, long at least 32-bit; in C99, long long as least 64-bit). This is the most that you can get if you want absolute portability, because there are architectures out there where you simply can't address memory in, say, 8-bit chunks (see SHARC for an example).
Consequently, while stdint.h defines types like int32_t, they are "conditionally supported", and so a C program that has a hard dependency on them is not universally portable. Types like int32_least_t and int32_fast_t are unconditionally supported, but they don't give you anything that you didn't have before.
Suppose you want to give a unique id to users of your application. Clearly 16bit is a bit small, you might get more than 65535 users. You'll probably want 32bits to be comfortable (unless you're google or facebook I guess).
So what type do you use? On any modern 32 or 64bit computer "unsigned int" would do the trick but if you want to be portable then you can't assume that "unsigned int" is more than 16 bits. So you have to use long instead.
But then that makes your type 64bits on modern computers. Completely overkill. If this id is used all over the place it will significantly increase the memory footprint and could hurt performance as well.
In truth when you write an application you never really care about the size of the CPU registers outside of device drivers. What you want to say is "I have this value that I estimate will max out at N, find me the fastest type where that fits".
So in the end, pre-stdint everybody would use machine-specific typedefs to do just that, portability be damned. In particular any big C library ended up doing that (glib has "gint8", "gint16", Qt has "qint8", "qint16, etc, libpng has "png_uint_16", "png_uint_32", etc...). Clearly people were not fine just using the minimum requirements of the standard.
>Types like int32_least_t and int32_fast_t are unconditionally supported, but they don't give you anything that you didn't have before.
But they do! Pre-C99 there's no way to say "I want a type that's at least 32bits and as fast as possible" or "I want a type that's at least 32bits but as small as possible". "int" could potentially be 16bits and "long" could be unnecessarily large, wasting RAM and cache. The only way to have this functionality was to use architecture-specific definitions.
I stand corrected on that point.
> Clearly people were not fine just using the minimum requirements of the standard.
Most of these typedefs are used to interop with some other standard or file format that requires that many bits exactly.
But even then I would argue that there was an overuse of such typedefs in C. I can think of several reasons for that:
First, there's a general lack of awareness that C does in fact provide "at least N bits" guarantee for most of its types. This comes up pretty often in questions on StackOverflow, and apparently there are still enough people surprised by the fact that e.g. long can never be 16-bit.
Partly, I think, it's because of the historical mess with int. Obviously, int is what people use by default, and the fact that it was 16-bit on many popular architectures in the past, and then became 32-bit on their successors, resulted in much broken code. I think that the lesson many took away from this is that all integer types in C are similarly broken, and switched to int32_t (or equivalent typedefs) just to avoid having to think about it.
Partly it's because of 64-bit ints. Standard C didn't have a 64-bit type for a long time. Popular implementations provided it as an extension, but in different ways - long long in most Unix compilers, __int64 in 32-bit DOS and Windows compilers. So if you ever needed 64 bits, you needed a typedef for that. Since most devs work on systems where word sizes are 8/16/32/64, they did the simplest and most obvious thing, and defined something like int64_t (as opposed to int64_least_t) - it just didn't occur to them that something beyond that was needed. And that set a precedent.
Then there was the part where long was made 64-bit in LP64 model, which meant that portable C had no "at least 32 bits, but no longer than it needs to be" type until C99. With the precedent established by int64_t, the logical step was to add int32_t, and int16_t as well for good measure.
And that's how we got where we are today. I would still argue that most of those libraries that use int32_t and similar types don't strictly need it. It's just a combination of historical factors, and also the fact that platforms where such types do exist comprise the vast majority of platforms, and all platforms that people care about. So there's no particular incentive to even think about how you'd write code for something else - why deal with the extra complexity, if you can just wave it off? Can't blame anyone for that.
And to me this shows clearly that we shouldn't be using C then.
If an arch can't address an 8 bit sized element there are two choices for what happens if you write:
char *a = "test"; char x = a[1];
Either char takes 32bytes or the a[1] read will shuffle the bytes to get a 32bit value whose least significant digits are a[1]
And saying that int32_t are "conditionally supported" is really proof we're making C worry about 8-bit microcontrolers when we're doing big application with it, it's trying too hard
I don't see why it's a problem, though? As noted earlier, C accommodates that. Sure, there's a lot of C code that's written with the assumption that chars are always 8-bit, because they usually are. But it's definitely possible to write portable C code that doesn't make such assumptions.
int32_t is required to be supported on any architecture on which one of the standard types is exactly 32-bit. Since long is required to be at least 32-bit, and any 8-bit microcontroller would have to support long, it would be 32-bit as well, and so it'd have int32_t (typedef'd to long). The only case where you wouldn't have it is either if the architecture has a word larger than 32 bits as its smallest addressable unit, or if it has non-8-bit bytes.
In practice, this is really not an issue, because you don't have to target the absolute most portable subset of C. The reason for making those features conditionally supported is so that when they are there, they behave the same. So you can say "my code runs on any platform that supports ISO C, and has int32_t in stdint.h". Not only that, but you can enforce it at compile-time with clear error messages, e.g.:
#ifndef INT32_MAX
#error "int32_t requrired"
#endif
Arguing that C shouldn't support microcontrollers seems a bit unfair. What should embedded software engineers use, if not "high level assembler"? There are plenty of modern languages that sacrifice performance in order to be fully hardware agnostic.
But you could still have any-bit integers even on an 8 bit processor, you'd just have to emulate them.
Clearly that's not really in the spirit of C which is probably why the standard doesn't force the compiler to implement those, instead relying on the coder to make a decision.
But that just proves my original point: C is not about portability. It's about writing fast code on any architecture. If portability was the concern the standard would make fixed-width integers mandatory and would define things like signed overflow, forcing the compilers to emulate the behavior when the hardware doesn't behave in the same way.
That's what portable languages do, that's what Rust does.
On ARM it is 8 bit + manipulation of value
> Arguing that C shouldn't support microcontrollers seems a bit unfair
No, I'm saying the opposite
What I want to say is that because it supports a big variety of processors it tries to do too much AND that our focus should be in more expressive languages in more powerful machines
C is great for a microcontroller with limited resources and inputs
(Ironically, this also shows just how much these types are actually used...)
Also, portability isn't a binary attribute. For every way two platforms vary, there are often a subset of states and transitions that are identical, and two disjoint subsets that are different.
As long as your inputs start out in the identical subset and don't wander too far, you're good to go. For example, if you never put a value above 32767 into an int, you don't really care whether your int is 16 or 32 bits in size. If that int is e.g. line number in a file, it may mean that your program works fine on most files, but only the 32-bit version works correctly on large files. And of course the cleverer you are the closer you're likely to skate to the edge of the common intersection.
Something that is, in some sense, truly portable is one that has a single specification that runs on all platforms the base implementation supports. Virtual machines and certain styles of language standard are often able to accomplish portability for a vast number of applications.
Edit: Not to mention libc, libm, and the like.
It gives options to the developer to target multiple platforms without extra effort from the users of those platforms.
I would argue that the C preprocessor is, for all intents and purposes, part of the C language. C is not quite practical without its preprocessor, and the preprocessor is not quite practical with any language other than C (or a derivative like C++).
This is markedly different from a language that, for example, guarantees the existence of integers of unbounded size. In this case, when working with integers, we make no mention of the platform to execute on. We are provided with an abstract guarantee that one can rely on regardless of the concrete platform.
Writing code in Common Lisp means you're writing something with semantics promised by the Common Lisp specification. Vendors implement the spec (perhaps using nasty #ifdefs), and developers write code against the spec. The spec is a contract, and from the point of view of the programmer, it's indifferent to platform change and so on (up to what the spec says is platform-dependent, like machine integer size or maximum array length).
Just because a particular implementation may not be considered portable, doesn't mean my program (which I may choose to run on that implementation) isn't portable.
Case in point is the recent article posted on HN about the platform specific details of getTimeMilliseconds() in Java.
My "ugly macros" are tested against my own implementation only. Compiler's are tested against thousands.
Are there any practical alternatives when that kind of portability is needed?
What about transpiling to C? I know Haskell and OCaml can be made to compile their code into C code that you can then pass on to a C compiler.
1. Manage resources with RAII (though, in C you could use non-portable attribute cleanup in similar manner).
2. Use type safe wrappers around builtin types like in [0] and [1].
3. Use containers with more extensive bounds checking and iteration validity checks [1].
This could help detect some of those bugs at runtime, or even possibly prevent them from being written in the first place. Use of uninitialized value could be prevented with types that require explicit initialization or have default one (Bug 1). Left shifting a negative value could have been caught at runtime (Bug 2). Bounds check could prevent uninitialized memory read (Bug 3) Type safe wrappers could prevent an accidental promotion from being written in the first place (Bug 5).
Though, you need to go out of your way to actually do all those things, not to mention that your code would integrate poorly with existing library ecosystem. IMHO choosing C++ alone doesn't improve safety of your programs compared to ones written in C all that much.
The sort of direct control one might look for is, as far as I know, only practically found in your processor's assembly language, and your operating system's collection of syscalls.
I think Rust, Common Lisp, OCaml, D, Haskell, and other languages give you a lot of benefits that are simply not worth giving up in a new crypto library, like safety.
I think writing timing-attack resistant code in Haskell would be very hard to impossible, at least without writing very unidiomatic code (basically "C in Haskell"). I'm happy to be proven wrong, though.
In fact, I believe something along the lines of this has already been done: https://cryptol.net
Edit: Whoah, why the hate? :(
Simply put, there are easier and cheaper ways to guarantee timings. Perhaps Haskell is even capable of harnessing them. (I'm thinking of the usual "no secret dependent branches", and "no secret dependent indices".)
I could run Rust code on a PlayStation and PocketStation (although I had to cheat a bit on the former because LLVM doesn't support MIPS I).
LLVM is not as widely ported as GCC (especially on older, deprecated hardware) but it's getting there.
Until the early 90's C had hardly any meaning outside big expensive UNIX boxes.
And it was already on its way out on Windows and OS/2, if it wasn't for the rise of FOSS software and its dependency on C.
In my experience most modern codebases tend to target POSIX systems (explicitly or implicitly). That gives you a subset of C to work with and makes your life easier. The exceptions are things like DSPs which can have rather non-standard layouts but you generally write very specific and unportable code for these anyway.
Of course if you want to be completely portable you can't assume that CHAR_BIT == 8 or that you can convert back and forth between function and data pointers but in practice a lot of software relies on this.
Even before stdint became part of the standard it was very common for programs and libraries to typedef their own "sized" integer types. It's the only reasonable way to deal with ints in C IMO, otherwise you can't assume that your ints are greater than 16bits (which is probably too tiny for many uses) so you're tempted to put "longs" everywhere. But then longs will be 64bits on modern architectures which could be overkill and reduce performance.
So in theory those variable-size integer types are interesting but in practice they're basically useless because you end up making assumptions, one way or an other. I think it was a good idea for Rust to get rid of them.
The ANSI C and C++ standards define the concept of abstract machine for the language semantics, just like in most languages.
Additionally you have the concepts of sequence points, the new memory model semantics for multi-threaded code and the beloved UB.
UB which doesn't exist in most languages, because their rather leave it implementation defined or lose the opportunity to target some strange CPU not able to support the language semantics.
Also Assembly doesn't has UB, making it ironic that it is safer to write straight Assembly at the expense of portability than C or C derived languages.
You just need to know your compiler flags/configuration to produce exact assembly output (if you want that). And about assembly not having UB, BSF and BSR are pretty good examples for that.
And I doubt anyone is regularly reviewing the produced Assembly every single time they change compilers.
Assembly doesn't have more than 200 documented cases that hardly any human is capable of remembering.
Edit: Sorry, wrote this too hastily and want to put it in perspective. While Ada is well-suited for cryptography and has some good implementations, it is probably not as secure as C crypto libraries in practice. The reason is that the implementations I know don't do OS-specific things like locking memory or preventing core dumps, and doing this in Ada is a bit harder than in C.
The author's lack of practical familiarity with the memory hierarchy, caching, and pipelining—evidenced by his surprise by the speed gained by fetching more than a byte at a time—also makes me suspicious of his understanding of the semantics of his program. (I understand that this is a form of ad hominem as it relates to arguing the correctness of software, but it's a consideration worth noting in a broader context of trust.)
It would be great if this was written in another language.
[0] Most "portable" code written in C is not portable. Look at any mature C project and see the layers and layers of macros and hacks to make things portable.