| 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>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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>
|
| |
|
|
|
|
|
|
|
| |
Define a cpu_halt() function which is architecture-specific but
platform-independent, and merge the multiple architecture-specific
implementations of the EFI cpu_nap() function into a single central
efi_cpu_nap() that uses cpu_halt() if applicable.
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>
|
| |
|
|
|
|
|
|
| |
Move the <gdbmach.h> file to <bits/gdbmach.h>, and provide a common
dummy implementation for all architectures that have not yet
implemented support for GDB.
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>
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
Define an API for executing very limited functions on application
processors in a multiprocessor system, along with an x86-only
implementation.
The normal iPXE runtime environment is effectively non-existent on
application processors. There is no ability to make firmware calls
(e.g. to write to a console), and there may be no stack space
available.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
The slightly incomprehensible LoongArch64 implementation for
bigint_subtract() is observed to produce incorrect results for some
input values.
Replace the suspicious LoongArch64 implementations of bigint_add(),
bigint_subtract(), bigint_rol() and bigint_ror(), and add a test case
for a subtraction that was producing an incorrect result with the
previous implementation.
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>
|
| |
|
|
|
|
| |
Signed-off-by: Xiaotian Wu <wuxiaotian@loongson.cn>
Modified-by: Michael Brown <mcb30@ipxe.org>
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
|
|
| |
Signed-off-by: Xiaotian Wu <wuxiaotian@loongson.cn>
Modified-by: Michael Brown <mcb30@ipxe.org>
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
As noted in commit 3c83843 ("[rng] Check for several functioning RTC
interrupts"), experimentation shows that Hyper-V cannot be trusted to
reliably generate RTC interrupts. (As noted in commit f3ba0fb
("[hyperv] Provide timer based on the 10MHz time reference count
MSR"), Hyper-V appears to suffer from a general problem in reliably
generating any legacy interrupts.) An alternative entropy source is
therefore required for an image that may be used in a Hyper-V Gen1
virtual machine.
The x86 RDRAND instruction provides a suitable alternative entropy
source, but may not be supported by all CPUs. We must therefore allow
for multiple entropy sources to be compiled in, with the single active
entropy source selected only at runtime.
Restructure the internal entropy API to allow a working entropy source
to be detected and chosen at runtime.
Enable the RDRAND entropy source for all x86 builds, since it is
likely to be substantially faster than any other source.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
|
|
Add support for building a LoongArch64 Linux userspace binary.
Signed-off-by: Xiaotian Wu <wuxiaotian@loongson.cn>
Modified-by: Michael Brown <mcb30@ipxe.org>
Signed-off-by: Michael Brown <mcb30@ipxe.org>
|
