ieee754.div_rem_sqrt_rsqrt package¶

Submodules¶

ieee754.div_rem_sqrt_rsqrt.algorithm module¶

Algorithms for div/rem/sqrt/rsqrt.

code for simulating/testing the various algorithms

class ieee754.div_rem_sqrt_rsqrt.algorithm.DivRem(dividend, divisor, bit_width, signed, log2_radix=3)¶

Bases: object

integer division/remainder following the RISC-V M extension.

NOT the same as the // or % operators

Attribute dividend:
	the dividend
Attribute divisor:
	the divisor
Attribute signed:
	if the inputs/outputs are signed instead of unsigned
Attribute quotient:
	the quotient
Attribute remainder:
	the remainder
Attribute divider:
	the base UnsignedDivRem

calculate_stage()¶

Calculate the next pipeline stage of the division.

Returns bool:	True if this is the last pipeline stage.

class ieee754.div_rem_sqrt_rsqrt.algorithm.Fixed(value, fract_width, bit_width, signed)¶

Bases: object

Fixed-point number.

the value is bits * 2 ** -fract_width

Attribute fract_width:
Attribute bits:	the bits of the fixed-point number
	the number of bits in the fractional portion
Attribute bit_width:
	the total number of bits
Attribute signed:
	if the type is signed

cmp(rhs)¶

Compare self with rhs.

Returns int:	returns -1 if self is less than rhs, 0 if they’re equal, and 1 for greater than. Returns NotImplemented for unimplemented cases

static from_bits(bits, fract_width, bit_width, signed)¶

Create a new Fixed.

Parameters:	bits – the bits of the fixed-point number fract_width – the number of bits in the fractional portion bit_width – the total number of bits signed – if the type is signed

with_bits(bits)¶

Create a new Fixed with the specified bits.

Parameters:	bits – the new bits.
Returns Fixed:	the new Fixed.

with_value(value)¶

Create a new Fixed with the specified value.

Parameters:	value – the new value.
Returns Fixed:	the new Fixed.

class ieee754.div_rem_sqrt_rsqrt.algorithm.FixedRSqrt(radicand, log2_radix=3)¶

Bases: object

Fixed-point Reciprocal-Square-Root/Remainder.

Attribute radicand:
	the radicand
Attribute root:	the reciprocal square root
Attribute radicand_root:
	`radicand * root`
Attribute radicand_root_squared:
	`radicand * root * root`
Attribute remainder:
	the remainder
Attribute log2_radix:
	the base-2 log of the operation radix. The number of bits of root that are calculated per pipeline stage.
Attribute current_shift:
	the current bit index

calculate()¶

Calculate the results of the reciprocal square root.

Returns:	self

calculate_stage()¶

Calculate the next pipeline stage of the operation.

Returns bool:	True if this is the last pipeline stage.

class ieee754.div_rem_sqrt_rsqrt.algorithm.FixedSqrt(radicand, log2_radix=3)¶

Bases: object

Fixed-point Square-Root/Remainder.

Attribute radicand:
	the radicand
Attribute root:	the square root
Attribute root_squared:
	the square of `root`
Attribute remainder:
	the remainder
Attribute log2_radix:
	the base-2 log of the operation radix. The number of bits of root that are calculated per pipeline stage.
Attribute current_shift:
	the current bit index

calculate()¶

Calculate the results of the square root.

Returns:	self

calculate_stage()¶

Calculate the next pipeline stage of the operation.

Returns bool:	True if this is the last pipeline stage.

class ieee754.div_rem_sqrt_rsqrt.algorithm.FixedUDivRemSqrtRSqrt(dividend, divisor_radicand, operation, bit_width, fract_width, log2_radix)¶

Bases: object

Combined class for computing fixed-point unsigned div/rem/sqrt/rsqrt.

Algorithm based on UnsignedDivRem, FixedSqrt, and FixedRSqrt.

Formulas solved are: * div/rem:

dividend == quotient_root * divisor_radicand

sqrt/rem:

divisor_radicand == quotient_root * quotient_root
rsqrt/rem:

1 == quotient_root * quotient_root * divisor_radicand

The remainder is the left-hand-side of the comparison minus the right-hand-side of the comparison in the above formulas.

Important: not all variables have the same bit-width or fract-width. For: instance, dividend has a bit-width of bit_width + fract_width and a fract-width of 2 * fract_width bits.

Attribute dividend:
	dividend for div/rem. Variable with a bit-width of `bit_width + fract_width` and a fract-width of `fract_width * 2` bits.
Attribute divisor_radicand:
	divisor for div/rem and radicand for sqrt/rsqrt. Variable with a bit-width of `bit_width` and a fract-width of `fract_width` bits.
Attribute operation:
	the `Operation` to be computed.
Attribute quotient_root:
	the quotient or root part of the result of the operation. Variable with a bit-width of `bit_width` and a fract-width of `fract_width` bits.
Attribute remainder:
	the remainder part of the result of the operation. Variable with a bit-width of `bit_width * 3` and a fract-width of `fract_width * 3` bits.
Attribute root_times_radicand:
	`quotient_root * divisor_radicand`. Variable with a bit-width of `bit_width * 2` and a fract-width of `fract_width * 2` bits.
Attribute compare_lhs:
	The left-hand-side of the comparison in the equation to be solved. Variable with a bit-width of `bit_width * 3` and a fract-width of `fract_width * 3` bits.
Attribute compare_rhs:
	The right-hand-side of the comparison in the equation to be solved. Variable with a bit-width of `bit_width * 3` and a fract-width of `fract_width * 3` bits.
Attribute bit_width:
	base bit-width. Constant int.
Attribute fract_width:
	base fract-width. Specifies location of base-2 radix point. Constant int.
Attribute log2_radix:
	number of bits of `quotient_root` that should be computed per pipeline stage (invocation of `calculate_stage`). Constant int.
Attribute current_shift:
	the current bit index. Variable int.

calculate()¶

Calculate the results of the operation.

Returns:	self

calculate_stage()¶

Calculate the next pipeline stage of the operation.

Returns bool:	True if this is the last pipeline stage.

class ieee754.div_rem_sqrt_rsqrt.algorithm.Operation¶

Bases: enum.Enum

Operation for FixedUDivRemSqrtRSqrt.

RSqrtRem = 'reciprocal-square-root/remainder'¶

SqrtRem = 'square-root/remainder'¶

UDivRem = 'unsigned-divide/remainder'¶

class ieee754.div_rem_sqrt_rsqrt.algorithm.RootRemainder(root, remainder)¶

Bases: object

A polynomial root and remainder.

Attribute remainder:
Attribute root:	the polynomial root.
	the remainder.

class ieee754.div_rem_sqrt_rsqrt.algorithm.UnsignedDivRem(dividend, divisor, bit_width, log2_radix=3)¶

Bases: object

Unsigned integer division/remainder following the RISC-V M extension.

NOT the same as the // or % operators

Attribute dividend:
	the dividend
Attribute remainder:
	the remainder
Attribute divisor:
	the divisor
Attribute bit_width:
	the bit width of the inputs/outputs
Attribute log2_radix:
	the base-2 log of the division radix. The number of bits of quotient that are calculated per pipeline stage.
Attribute quotient:
	the quotient
Attribute quotient_times_divisor:
	`quotient * divisor`
Attribute current_shift:
	the current bit index

calculate()¶

Calculate the results of the division.

Returns:	self

calculate_stage()¶

Calculate the next pipeline stage of the division.

Returns bool:	True if this is the last pipeline stage.

ieee754.div_rem_sqrt_rsqrt.algorithm.div_rem(dividend, divisor, bit_width, signed)¶

Compute the quotient/remainder following the RISC-V M extension.

NOT the same as the // or % operators

ieee754.div_rem_sqrt_rsqrt.algorithm.fixed_rsqrt(radicand)¶

Compute the Reciprocal Square Root and Remainder.

Solves the polynomial 1 - x * x * radicand == 0

Returns RootRemainder:
Parameters:	radicand – the `Fixed` to take the reciprocal square root of.

ieee754.div_rem_sqrt_rsqrt.algorithm.fixed_sqrt(radicand)¶

Compute the Square Root and Remainder.

Solves the polynomial radicand - x * x == 0

Returns RootRemainder:
Parameters:	radicand – the `Fixed` to take the square root of.

ieee754.div_rem_sqrt_rsqrt.core module¶

Core of the div/rem/sqrt/rsqrt pipeline.

Special case handling, input/output conversion, and muxid handling are handled outside of these classes.

Algorithms based on algorithm.FixedUDivRemSqrtRSqrt.

Formulas solved are: * div/rem:

dividend == quotient_root * divisor_radicand

sqrt/rem:

divisor_radicand == quotient_root * quotient_root
rsqrt/rem:

1 == quotient_root * quotient_root * divisor_radicand

The remainder is the left-hand-side of the comparison minus the right-hand-side of the comparison in the above formulas.

ieee754.div_rem_sqrt_rsqrt.core.DP¶: alias of ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreOperation

class ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreCalculateStage(core_config, stage_index)¶

Bases: nmigen.hdl.ir.Elaboratable

Calculate Stage of the core of the div/rem/sqrt/rsqrt pipeline.

elaborate(platform)¶: Elaborate into Module.

ispec()¶: Get the input spec for this pipeline stage.

ospec()¶: Get the output spec for this pipeline stage.

process(i)¶: Pipeline stage process.

setup(m, i)¶: Pipeline stage setup.

class ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreConfig(bit_width, fract_width, log2_radix, supported=None)¶

Bases: object

Configuration for core of the div/rem/sqrt/rsqrt pipeline.

Attribute bit_width:
	base bit-width.
Attribute fract_width:
	base fract-width. Specifies location of base-2 radix point.
Attribute log2_radix:
	number of bits of `quotient_root` that should be computed per pipeline stage.

n_stages¶: Get the number of DivPipeCoreCalculateStage needed.

class ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreFinalStage(core_config)¶

Bases: nmigen.hdl.ir.Elaboratable

Final Stage of the core of the div/rem/sqrt/rsqrt pipeline.

elaborate(platform)¶: Elaborate into Module.

ispec()¶: Get the input spec for this pipeline stage.

ospec()¶: Get the output spec for this pipeline stage.

process(i)¶: Pipeline stage process.

setup(m, i)¶: Pipeline stage setup.

class ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreInputData(core_config, reset_less=True)¶

Bases: object

input data type for DivPipeCore.

Attribute core_config:
	`DivPipeCoreConfig` instance describing the configuration to be used.
Attribute dividend:
	dividend for div/rem. Signal with a bit-width of `core_config.bit_width + core_config.fract_width` and a fract-width of `core_config.fract_width * 2` bits.
Attribute divisor_radicand:
	divisor for div/rem and radicand for sqrt/rsqrt. Signal with a bit-width of `core_config.bit_width` and a fract-width of `core_config.fract_width` bits.
Attribute operation:
	the `DivPipeCoreOperation` to be computed.

eq(rhs)¶: Assign member signals.

class ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreInterstageData(core_config, reset_less=True)¶

Bases: object

interstage data type for DivPipeCore.

Attribute core_config:
	`DivPipeCoreConfig` instance describing the configuration to be used.
Attribute divisor_radicand:
	divisor for div/rem and radicand for sqrt/rsqrt. Signal with a bit-width of `core_config.bit_width` and a fract-width of `core_config.fract_width` bits.
Attribute operation:
	the `DivPipeCoreOperation` to be computed.
Attribute quotient_root:
	the quotient or root part of the result of the operation. Signal with a bit-width of `core_config.bit_width` and a fract-width of `core_config.fract_width` bits.
Attribute root_times_radicand:
	`quotient_root * divisor_radicand`. Signal with a bit-width of `core_config.bit_width * 2` and a fract-width of `core_config.fract_width * 2` bits.
Attribute compare_lhs:
	The left-hand-side of the comparison in the equation to be solved. Signal with a bit-width of `core_config.bit_width * 3` and a fract-width of `core_config.fract_width * 3` bits.
Attribute compare_rhs:
	The right-hand-side of the comparison in the equation to be solved. Signal with a bit-width of `core_config.bit_width * 3` and a fract-width of `core_config.fract_width * 3` bits.

eq(rhs)¶: Assign member signals.

class ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreOperation¶

Bases: enum.Enum

Operation for DivPipeCore.

Attribute UDivRem:
	unsigned divide/remainder.
Attribute SqrtRem:
	square-root/remainder.
Attribute RSqrtRem:
	reciprocal-square-root/remainder.

RSqrtRem = 2¶

SqrtRem = 0¶

UDivRem = 1¶

class ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreOutputData(core_config, reset_less=True)¶

Bases: object

output data type for DivPipeCore.

Attribute core_config:
	`DivPipeCoreConfig` instance describing the configuration to be used.
Attribute quotient_root:
	the quotient or root part of the result of the operation. Signal with a bit-width of `core_config.bit_width` and a fract-width of `core_config.fract_width` bits.
Attribute remainder:
	the remainder part of the result of the operation. Signal with a bit-width of `core_config.bit_width * 3` and a fract-width of `core_config.fract_width * 3` bits.

eq(rhs)¶: Assign member signals.

class ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreSetupStage(core_config)¶

Bases: nmigen.hdl.ir.Elaboratable

Setup Stage of the core of the div/rem/sqrt/rsqrt pipeline.

elaborate(platform)¶: Elaborate into Module.

ispec()¶: Get the input spec for this pipeline stage.

ospec()¶: Get the output spec for this pipeline stage.

process(i)¶: Pipeline stage process.

setup(m, i)¶: Pipeline stage setup.

class ieee754.div_rem_sqrt_rsqrt.core.Trial(core_config, trial_bits, current_shift, log2_radix)¶

Bases: nmigen.hdl.ir.Elaboratable

elaborate(platform)¶

ieee754.div_rem_sqrt_rsqrt.div_pipe module¶

div/rem/sqrt/rsqrt pipeline.

class ieee754.div_rem_sqrt_rsqrt.div_pipe.DivPipeBaseData(pspec)¶

Bases: object

input data base type for DivPipe.

Attribute out_do_z:
Attribute z:	a convenient way to carry the sign and exponent through the pipeline from when they were computed right at the start.
	FIXME: document
Attribute oz:	FIXME: document
Attribute ctx:	FIXME: document
Attribute muxid:
	FIXME: document Alias of `ctx.muxid`.
Attribute config:
	the `DivPipeConfig` instance.

eq(rhs)¶: Assign member signals.

class ieee754.div_rem_sqrt_rsqrt.div_pipe.DivPipeBaseStage¶

Bases: object

Base Mix-in for DivPipe*Stage.

class ieee754.div_rem_sqrt_rsqrt.div_pipe.DivPipeCalculateStage(pspec, stage_idx)¶

Bases: ieee754.div_rem_sqrt_rsqrt.div_pipe.DivPipeBaseStage, ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreCalculateStage

FIXME: add docs.

elaborate(platform)¶: Elaborate into Module.

ispec()¶: Get the input spec for this pipeline stage.

ospec()¶: Get the output spec for this pipeline stage.

class ieee754.div_rem_sqrt_rsqrt.div_pipe.DivPipeFinalStage(pspec)¶

Bases: ieee754.div_rem_sqrt_rsqrt.div_pipe.DivPipeBaseStage, ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreFinalStage

FIXME: add docs.

elaborate(platform)¶: Elaborate into Module.

ispec()¶: Get the input spec for this pipeline stage.

ospec()¶: Get the output spec for this pipeline stage.

class ieee754.div_rem_sqrt_rsqrt.div_pipe.DivPipeInputData(pspec)¶

Bases: ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreInputData, ieee754.div_rem_sqrt_rsqrt.div_pipe.DivPipeBaseData

input data type for DivPipe.

eq(rhs)¶: Assign member signals.

class ieee754.div_rem_sqrt_rsqrt.div_pipe.DivPipeInterstageData(pspec)¶

Bases: ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreInterstageData, ieee754.div_rem_sqrt_rsqrt.div_pipe.DivPipeBaseData

interstage data type for DivPipe.

eq(rhs)¶: Assign member signals.

class ieee754.div_rem_sqrt_rsqrt.div_pipe.DivPipeOutputData(pspec)¶

Bases: ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreOutputData, ieee754.div_rem_sqrt_rsqrt.div_pipe.DivPipeBaseData

output data type for DivPipe.

eq(rhs)¶: Assign member signals.

class ieee754.div_rem_sqrt_rsqrt.div_pipe.DivPipeSetupStage(pspec)¶

Bases: ieee754.div_rem_sqrt_rsqrt.div_pipe.DivPipeBaseStage, ieee754.div_rem_sqrt_rsqrt.core.DivPipeCoreSetupStage

FIXME: add docs.

elaborate(platform)¶: Elaborate into Module.

ispec()¶: Get the input spec for this pipeline stage.

ospec()¶: Get the output spec for this pipeline stage.

ieee754.div_rem_sqrt_rsqrt.test_algorithm module¶

class ieee754.div_rem_sqrt_rsqrt.test_algorithm.TestDivRem(methodName='runTest')¶

Bases: unittest.case.TestCase

helper(log2_radix)¶

test_radix_16()¶

test_radix_2()¶

test_radix_4()¶

test_radix_8()¶

class ieee754.div_rem_sqrt_rsqrt.test_algorithm.TestDivRemFn(methodName='runTest')¶

Bases: unittest.case.TestCase

test_signed()¶

test_unsigned()¶

class ieee754.div_rem_sqrt_rsqrt.test_algorithm.TestFixed(methodName='runTest')¶

Bases: unittest.case.TestCase

binary_op_test_helper(operation, is_fixed=True, width_combine_op=<built-in function max>, adjust_bits_op=None)¶

static get_test_values(max_bit_width, include_int)¶

helper_tst_from_bits(bit_width, fract_width)¶

test_abs()¶

test_add()¶

test_and()¶

test_bool()¶

test_ceil()¶

test_cmp()¶

test_constructor()¶

test_eq()¶

test_float()¶

test_floor()¶

test_from_bits()¶

test_ge()¶

test_gt()¶

test_int()¶

test_le()¶

test_lt()¶

test_mul()¶

test_ne()¶

test_neg()¶

test_not()¶

test_or()¶

test_pos()¶

test_repr()¶

test_str()¶

test_sub()¶

test_trunc()¶

test_xor()¶

class ieee754.div_rem_sqrt_rsqrt.test_algorithm.TestFixedRSqrt(methodName='runTest')¶

Bases: unittest.case.TestCase

helper(log2_radix)¶

test_radix_16()¶

test_radix_2()¶

test_radix_4()¶

test_radix_8()¶

class ieee754.div_rem_sqrt_rsqrt.test_algorithm.TestFixedRSqrtFn(methodName='runTest')¶

Bases: unittest.case.TestCase

test()¶

test2()¶

test_misc_cases()¶

class ieee754.div_rem_sqrt_rsqrt.test_algorithm.TestFixedSqrt(methodName='runTest')¶

Bases: unittest.case.TestCase

helper(log2_radix)¶

test_radix_16()¶

test_radix_2()¶

test_radix_4()¶

test_radix_8()¶

class ieee754.div_rem_sqrt_rsqrt.test_algorithm.TestFixedSqrtFn(methodName='runTest')¶

Bases: unittest.case.TestCase

test_misc_cases()¶

test_on_fixed()¶

test_on_ints()¶

class ieee754.div_rem_sqrt_rsqrt.test_algorithm.TestFixedUDivRemSqrtRSqrt(methodName='runTest')¶

Bases: unittest.case.TestCase

check_invariants(dividend, divisor_radicand, operation, bit_width, fract_width, log2_radix, obj)¶

handle_case(dividend, divisor_radicand, operation, bit_width, fract_width, log2_radix)¶

helper(log2_radix, operation)¶

static show_fixed(bits, fract_width, bit_width)¶

test_fract_div()¶

test_int_div()¶

test_radix_16_RSqrt()¶

test_radix_16_Sqrt()¶

test_radix_16_UDiv()¶

test_radix_2_RSqrt()¶

test_radix_2_Sqrt()¶

test_radix_2_UDiv()¶

test_radix_4_RSqrt()¶

test_radix_4_Sqrt()¶

test_radix_4_UDiv()¶

test_radix_8_RSqrt()¶

test_radix_8_Sqrt()¶

test_radix_8_UDiv()¶

class ieee754.div_rem_sqrt_rsqrt.test_algorithm.TestUnsignedDivRem(methodName='runTest')¶

Bases: unittest.case.TestCase

helper(log2_radix)¶

test_radix_16()¶

test_radix_2()¶

test_radix_4()¶

test_radix_8()¶

ieee754.div_rem_sqrt_rsqrt.test_core module¶

class ieee754.div_rem_sqrt_rsqrt.test_core.DivPipeCoreTestPipeline(core_config, sync)¶

Bases: nmigen.hdl.ir.Elaboratable

elaborate(platform)¶

traces()¶

class ieee754.div_rem_sqrt_rsqrt.test_core.TestCaseData(dividend, divisor_radicand, alg_op, quotient_root, remainder, core_config)¶

Bases: object

core_op¶

class ieee754.div_rem_sqrt_rsqrt.test_core.TestDivPipeCore(methodName='runTest')¶

Bases: unittest.case.TestCase

handle_config(core_config, test_cases=None, sync=True)¶

test_bit_width_2_fract_width_1_radix_2()¶

test_bit_width_2_fract_width_1_radix_2_comb()¶

test_bit_width_32_fract_width_24_radix_8()¶

test_bit_width_32_fract_width_24_radix_8_comb()¶

test_bit_width_32_fract_width_28_radix_8()¶

test_bit_width_32_fract_width_28_radix_8_comb()¶

test_bit_width_8_fract_width_4_radix_2()¶

test_bit_width_8_fract_width_4_radix_2_comb()¶

test_bit_width_8_fract_width_4_radix_4()¶

test_bit_width_8_fract_width_4_radix_4_comb()¶

test_bit_width_8_fract_width_4_radix_4_comb_div_only()¶

test_bit_width_8_fract_width_4_radix_4_div_only()¶

class ieee754.div_rem_sqrt_rsqrt.test_core.TestShiftedInts(methodName='runTest')¶

Bases: unittest.case.TestCase

test()¶

ieee754.div_rem_sqrt_rsqrt.test_core.generate_test_case(core_config, dividend, divisor_radicand, alg_op)¶

ieee754.div_rem_sqrt_rsqrt.test_core.get_core_op(alg_op)¶

ieee754.div_rem_sqrt_rsqrt.test_core.get_test_cases(core_config, dividends=None, divisors=None, radicands=None)¶

ieee754.div_rem_sqrt_rsqrt.test_core.partitioned_ints(bit_width)¶: Get ints with all 1s on one side and 0s on the other.

ieee754.div_rem_sqrt_rsqrt.test_core.shifted_ints(total_bits, int_bits)¶

Generate a sequence like a generalized binary version of A037124.

See https://oeis.org/A037124

Generates the sequence of all non-negative integers n in ascending order with no repeats where n < (1 << total_bits) and n == (v << i) where i is a non-negative integer and v is a non-negative integer less than 1 << int_bits.

ieee754.div_rem_sqrt_rsqrt.test_core.show_fixed(bits, fract_width, bit_width)¶

ieee754.div_rem_sqrt_rsqrt.test_core.trace_process(process, prefix='trace:', silent=False)¶

ieee754.div_rem_sqrt_rsqrt package¶

Submodules¶

ieee754.div_rem_sqrt_rsqrt.algorithm module¶

ieee754.div_rem_sqrt_rsqrt.core module¶

ieee754.div_rem_sqrt_rsqrt.div_pipe module¶

ieee754.div_rem_sqrt_rsqrt.test_algorithm module¶

ieee754.div_rem_sqrt_rsqrt.test_core module¶

Module contents¶