SHA-1 in FORTRAN
Nate
algorithm? I need to do hmac-sha1 hashes for a project but I would
rather not have to compile together a C function just for this. I was
going to try to port something but hashing is a complicated business.
Thanks,
Nate
glen herrmannsfeldt
I would say the easiest is direct translation either the C source,
or the pseudocode in, for example, the wikipedia page.
You have to make a few assumptions that the Fortran standard does
not make, such as the existence of (at least) a 32 bit INTEGER type.
It is much easier if you can assume twos complement arithmetic,
and that carries are ignored (that is, wrap on overflow).
The rotate operation can be done with combinations of left shift,
right shift, AND and OR.
-- glen
Ron Shepard
glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> The rotate operation can be done with combinations of left shift,
> right shift, AND and OR.
Is this the same as ishftc()? I think that is a standard intrinsic,
and has been so since 1979 if you count the milstd standard, and
since f90 otherwise.
$.02 -Ron Shepard
glen herrmannsfeldt
It is, with the appropriate third argument. Well, since Fortran
makes no guarantee on the maximum bit width of INTEGER types,
it is hard to use ishftc() without specifying the width.
SHA1 uses a 32 bit rotation in a few places.
In one check, it seems that gfortran generates IOR, IAND, IEOR,
and ISHFT inline, but ISHFTC with a subroutine call. Two calls
to ISHFT, in that case, is likely faster than ISHFTC.
-- glen
steve
> In one check, it seems that gfortran generates IOR, IAND, IEOR,
> and ISHFT inline, but ISHFTC with a subroutine call. Two calls
> to ISHFT, in that case, is likely faster than ISHFTC.
>
Source code?
Given the right source gfortran won't produce anything except
the answer (hint, constant folding).
--
steve
glen herrmannsfeldt
> On Feb 9, 10:13?pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
>> In one check, it seems that gfortran generates IOR, IAND, IEOR,
>> to ISHFT, in that case, is likely faster than ISHFTC.
> Source code?
! test the generated code for some simple functions
integer i,j
read(*,*) i,j
write(*,*) iand(i,j),ior(i,j),ieor(i,j),ishft(i,-4),ishftc(i,4,32)
end
> Given the right source gfortran won't produce anything except
> the answer (hint, constant folding).
Yes, to avoid that I read in i and j. I used constants for
the second and third argument of ishftc(), as that is a common use.
The problem of benchmarks and constant folding is an old one.
-- glen
Dick Hendrickson
inquiry functions to force either a compile time or run time abort
if the integer size isn't 32 bits if it is important to the algorithm.
Dick Hendrickson
glen herrmannsfeldt
> glen herrmannsfeldt wrote:
(snip regarding ISHFTC)
>> It is, with the appropriate third argument. Well, since Fortran
>> makes no guarantee on the maximum bit width of INTEGER types,
>> it is hard to use ishftc() without specifying the width.
>> SHA1 uses a 32 bit rotation in a few places.
>> In one check, it seems that gfortran generates IOR, IAND, IEOR,
>> and ISHFT inline, but ISHFTC with a subroutine call. Two calls
>> to ISHFT, in that case, is likely faster than ISHFTC.
> True, there's no guarantee. But I think you can use the various
> inquiry functions to force either a compile time or run time abort
> if the integer size isn't 32 bits if it is important to the algorithm.
Most algorithms that use bitwise logical operations only need a wide
enough data type. Circular shift usually needs the exact width.
Since ISHFT guarantees to shift in zeros, you can do the equivalent
of circular shift with two ISHFT and one IOR. That is likely
faster than the overhead of a subroutine call.
-- glen
Richard Maine
That's also the kind of micro-optimization that I recommend people avoid
in most situations. It is completely compiler dependent whether it is
even an optimization at all. If you have observed that there is a
consistently faster way than what a compiler does on its own, perhaps a
performance bug report to the compiler developers would be in order.
Hacking around a performance problem in one compiler is reasonably
likely to slow things down in another (or even a subsequent release of
the same compiler). That kind of thing happens regularly.
Unless you can observe (not just predict) the performance difference in
an actual application, and also see that the performance difference is
important, I recommend coding for clarity and simplicity. It often ends
up faster in the long run anyway (even more so when you add
consideration of debugging time). This is classic advice from
prehistoric days, but it still applies - if anything more so now than
then.
--
Richard Maine | Good judgment comes from experience;
email: last name at domain . net | experience comes from bad judgment.
domain: summertriangle | -- Mark Twain
Zaak
Now here is where I would love some feedback:
1) Is it reasonable to assume a two's compliment integer addition? Does anyone know of any common compilers or platforms where this is not the case?
2) Is my understanding of two's compliment integer addition correct in that it's implementation will be the same as unsigned integer addition, it is merely the interpretation of the binary words that changes? (e.g. under a 3 bit word system 010 + 011 = 101 which in unsigned integer arithmetic is 2 + 3 = 5 and is an overflow in two's complement 2 + 3 = -3. Or a case which would demonstrate the required modulo 2^w = modulo 8: 110 + 011 = 1001 = 001 which for unsigned integers would be 6 + 3 = 9 modulo 8 = 1 and for two's compliment would be -2 + 3 = 1. Please forgive any potential errors, I am doing the binary arithmetic in my head as I type this.)
3) What special care must be take to initialize the constant in a Fortran/two's compliment framework?
4) Will compilers generate code that halts on integer overflow?
5) Have unsigned integers ever been considered for addition to the standard?
This is a question that I have thought a lot about and would very much appreciate some feedback on.
Wolfgang Kilian
> On Tuesday, February 9, 2010 12:02:30 PM UTC-5, Nate wrote:
>> Anyone ever heard of a pure fortran implementation of the SHA-1 hash
>> algorithm? I need to do hmac-sha1 hashes for a project but I would
>> rather not have to compile together a C function just for this. I was
>> going to try to port something but hashing is a complicated business.
>>
>> Thanks,
>> Nate
>
> So, from a standards/Fortran perspective, it seems that the biggest sticking point is that there is no unsigned integer arithmetic guaranteeing that addition is modulo 2^w where w is the number of bits in your integer representation. I believe all the other operations specified in SHA1 and SHA2 are natively supported by the standard.
>
> Now here is where I would love some feedback:
>
> 1) Is it reasonable to assume a two's compliment integer addition? Does anyone know of any common compilers or platforms where this is not the case?
a thread in this newsgroup
> 2) Is my understanding of two's compliment integer addition correct in that it's implementation will be the same as unsigned integer addition, it is merely the interpretation of the binary words that changes? (e.g. under a 3 bit word system 010 + 011 = 101 which in unsigned integer arithmetic is 2 + 3 = 5 and is an overflow in two's complement 2 + 3 = -3. Or a case which would demonstrate the required modulo 2^w = modulo 8: 110 + 011 = 1001 = 001 which for unsigned integers would be 6 + 3 = 9 modulo 8 = 1 and for two's compliment would be -2 + 3 = 1. Please forgive any potential errors, I am doing the binary arithmetic in my head as I type this.)
integer addition (with or w/o overflow) which is composed of the
bit-handling functions in Fortran. A clean implementation might
introduce a derived type (possibly using a larger integer type
internally) and overload operators as needed.
> 3) What special care must be take to initialize the constant in a Fortran/two's compliment framework?
>
> 4) Will compilers generate code that halts on integer overflow?
considered a feature. It should be possible to work around this, however.
> 5) Have unsigned integers ever been considered for addition to the standard?
> This is a question that I have thought a lot about and would very much appreciate some feedback on.
issues. Apart from the NAG compiler complaining on assigning some
constants, this has worked flawlessly. But we didn't meet a machine
other than two's complement. If one appears on our radar (unit tests
should fail then), I would re-implement this via derived types and
overloading, see above.
-- Wolfgang
--
E-mail: firstnameini...@domain.de
Domain: yahoo
Arjen Markus
...
> integer addition (with or w/o overflow) which is composed of the
> bit-handling functions in Fortran. A clean implementation might
> introduce a derived type (possibly using a larger integer type
> internally) and overload operators as needed.
>
> > 5) Have unsigned integers ever been considered for addition to the standard?
>
>
>
> Good question ...
>
will require experimentation, but it is available.
Regards,
Arjen
Zaak
> I have implemented an unsigned integers module in Fortran. See: http://flibs.sf.net. Whether that is efficient enough, is a matter that
> will require experimentation, but it is available.
Thanks for the reply.
Arjen, it seems that you have not uploaded a source/project tarball for flibs recently, so the documentation is ahead of the files available through direct download, which caused me some confusion at first, until I figured out how to grab the files via CVS.
It seems that your implementation confirms my understanding of two's complement addition versus unsigned integer addition, modulo any compiler specific warnings/errors caused by overflow. Fortunately, I think that addition is the only integer arithmetic required by SHA2, all other operations are bitwise and have a 1 to 1 mapping with the associated C operations.
P.S. I'm enjoying your book. I've read your Fortran forum contributions from time to time, but the book is a nice collection of all the work you've contributed, thanks for publishing it!
Wolfgang:
> integer addition (with or w/o overflow) which is composed of the
> bit-handling functions in Fortran. A clean implementation might
> introduce a derived type (possibly using a larger integer type
> internally) and overload operators as needed.
robert....@oracle.com
> 5) Have unsigned integers ever been considered for addition to the standard?
>
> This is a question that I have thought a lot about and would very much appreciate some feedback on.
Of course, there were many other objections. One was that Sun's proposal made UNSIGNED a new type. Members of the committee said that any implementation is free to add unsigned integers now as a new KIND of INTEGER. Of course, there is the small problem that -1 is required to be a model value of any integer type, but that did not bother them.
Oracle Solaris Studio Fortran, which is available at no cost for both Solaris and Linux, has supported unsigned integers for several releases.
Bob Corbett
Arjen Markus
>
>
>
> > I have implemented an unsigned integers module in Fortran. See: http://flibs.sf.net. Whether that is efficient enough, is a matter that
>
> > will require experimentation, but it is available.
>
>
>
> Arjen & Wolfgang,
>
> Thanks for the reply.
>
>
>
> Arjen, it seems that you have not uploaded a source/project tarball for flibs recently, so the documentation is ahead of the files available through direct download, which caused me some confusion at first, until I figured out how to grab the files via CVS.
>
difficult, but it takes a bit of careful work. I will not promise anything,
but I will try to get a new version out somewhere next month. It is long
overdue.
>
> It seems that your implementation confirms my understanding of two's complement addition versus unsigned integer addition, modulo any compiler specific warnings/errors caused by overflow. Fortunately, I think that addition is the only integer arithmetic required by SHA2, all other operations are bitwise and have a 1 to 1 mapping with the associated C operations.
>
>
>
> P.S. I'm enjoying your book. I've read your Fortran forum contributions from time to time, but the book is a nice collection of all the work you've contributed, thanks for publishing it!
>
I am glad you find it useful.
Regards,
Arjen