| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
| |
Expose the bit shifted out as a result of shifting a big integer left
or right.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
|
|
|
|
| |
Expose the effective carry (or borrow) out flag from big integer
addition and subtraction, and use this to elide an explicit bit test
when performing x25519 reduction.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
|
|
|
|
|
|
|
| |
Every architecture uses the same implementation for bigint_is_set(),
and there is no reason to suspect that a future CPU architecture will
provide a more efficient way to implement this operation.
Simplify the code by providing a single architecture-independent
implementation of bigint_is_set().
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
|
|
|
|
|
|
|
| |
The big integer shift operations are misleadingly described as
rotations since the original x86 implementations are essentially
trivial loops around the relevant rotate-through-carry instruction.
The overall operation performed is a shift rather than a rotation.
Update the function names and descriptions to reflect this.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
|
|
|
|
|
|
|
|
| |
An n-bit multiplication product may be added to up to two n-bit
integers without exceeding the range of a (2n)-bit integer:
(2^n - 1)*(2^n - 1) + (2^n - 1) + (2^n - 1) = 2^(2n) - 1
Exploit this to perform big integer multiplication in constant time
without requiring the caller to provide temporary carry space.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
|
|
|
|
|
|
|
|
| |
Reading from PMCCNTR causes an undefined instruction exception when
running in PL0 (e.g. as a Linux userspace binary), unless the
PMUSERENR.EN bit is set.
Restructure profile_timestamp() for 32-bit ARM to perform an
availability check on the first invocation, with subsequent
invocations returning zero if PMCCNTR could not be enabled.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
All consumers of profile_timestamp() currently treat the value as an
unsigned long. Only the elapsed number of ticks is ever relevant: the
absolute value of the timestamp is not used. Profiling is used to
measure short durations that are generally fewer than a million CPU
cycles, for which an unsigned long is easily large enough.
Standardise the return type of profile_timestamp() as unsigned long
across all CPU architectures. This allows 32-bit architectures such
as i386 and riscv32 to omit all logic associated with retrieving the
upper 32 bits of the 64-bit hardware counter, which simplifies the
code and allows riscv32 and riscv64 to share the same implementation.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Big integer multiplication currently performs immediate carry
propagation from each step of the long multiplication, relying on the
fact that the overall result has a known maximum value to minimise the
number of carries performed without ever needing to explicitly check
against the result buffer size.
This is not a constant-time algorithm, since the number of carries
performed will be a function of the input values. We could make it
constant-time by always continuing to propagate the carry until
reaching the end of the result buffer, but this would introduce a
large number of redundant zero carries.
Require callers of bigint_multiply() to provide a temporary carry
storage buffer, of the same size as the result buffer. This allows
the carry-out from the accumulation of each double-element product to
be accumulated in the temporary carry space, and then added in via a
single call to bigint_add() after the multiplication is complete.
Since the structure of big integer multiplication is identical across
all current CPU architectures, provide a single shared implementation
of bigint_multiply(). The architecture-specific operation then
becomes the multiplication of two big integer elements and the
accumulation of the double-element product.
Note that any intermediate carry arising from accumulating the lower
half of the double-element product may be added to the upper half of
the double-element product without risk of overflow, since the result
of multiplying two n-bit integers can never have all n bits set in its
upper half. This simplifies the carry calculations for architectures
such as RISC-V and LoongArch64 that do not have a carry flag.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
|
|
|
|
|
|
|
| |
The definitions of the setjmp() and longjmp() functions are common to
all architectures, with only the definition of the jump buffer
structure being architecture-specific.
Move the architecture-specific portions to bits/setjmp.h and provide a
common setjmp.h for the function definitions.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
|
|
|
|
| |
Simplify the process of adding a new CPU architecture by providing
common implementations of typically empty architecture-specific header
files.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
|
|
|
|
|
|
|
| |
Big integer multiplication is currently used only as part of modular
exponentiation, where both multiplicand and multiplier will be the
same size.
Relax this requirement to allow for the use of big integer
multiplication in other contexts.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Over the years, the undocumented operand modifier used to produce the
unprefixed constant values in __einfo_error() has varied from "%c0" to
"%a0" in commit 1a77466 ("[build] Fix use of inline assembly on GCC
4.8 ARM64 builds") and back to "%c0" in commit 3fb3ffc ("[build] Fix
use of inline assembly on GCC 8 ARM64 builds"), according to the
evolving demands of the toolchain.
LoongArch64 suffers from a similar issue: GCC 13 will allow either,
but the currently released GCC 12 allows only the "%a0" form.
Introduce a macro ASM_NO_PREFIX, defined in bits/compiler.h, to
abstract away this difference and allow different architectures to use
different operand modifiers.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
| |
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
| |
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
|
|
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
