From 30567a3a66c5deb2ce717398d663408bed685756 Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Tue, 8 Nov 2022 00:00:54 -0800 Subject: [PATCH] add EvalOpValueRange --- src/bigint_presentation_code/toom_cook.py | 39 ++++++++++++++++++++--- 1 file changed, 35 insertions(+), 4 deletions(-) diff --git a/src/bigint_presentation_code/toom_cook.py b/src/bigint_presentation_code/toom_cook.py index 7e9748c..03f3e93 100644 --- a/src/bigint_presentation_code/toom_cook.py +++ b/src/bigint_presentation_code/toom_cook.py @@ -1,14 +1,15 @@ """ Toom-Cook multiplication algorithm generator for SVP64 """ -from abc import abstractmethod +from abc import ABCMeta, abstractmethod from enum import Enum from fractions import Fraction from typing import Any, Generic, Iterable, Mapping, TypeVar, Union from nmutil.plain_data import plain_data -from bigint_presentation_code.compiler_ir import Fn, OpKind, SSAVal +from bigint_presentation_code.compiler_ir import (GPR_SIZE_IN_BITS, Fn, OpKind, + SSAVal) from bigint_presentation_code.matrix import Matrix from bigint_presentation_code.type_util import Literal, final @@ -22,7 +23,7 @@ class PointAtInfinity(Enum): POINT_AT_INFINITY = PointAtInfinity.POINT_AT_INFINITY -WORD_BITS = 64 +WORD_BITS = GPR_SIZE_IN_BITS _EvalOpPolyCoefficients = Union["Mapping[int | None, Fraction | int]", "EvalOpPoly", Fraction, int, None] @@ -158,12 +159,42 @@ class EvalOpPoly: return f"EvalOpPoly({self.coefficients})" +@plain_data(frozen=True, unsafe_hash=True) +class EvalOpValueRange: + __slots__ = ("eval_op", "inputs_words", "min_value", "max_value", + "is_signed") + + def __init__(self, eval_op, inputs_words): + # type: (EvalOp[Any, Any], Iterable[int]) -> None + super().__init__() + self.eval_op = eval_op + self.inputs_words = tuple(inputs_words) + for words in self.inputs_words: + if words <= 0: + raise ValueError(f"invalid word count: {words}") + min_value = max_value = eval_op.poly.const_coeff + for var, coeff in enumerate(eval_op.poly.var_coeffs): + if coeff == 0: + continue + var_min = 0 + var_max = (1 << self.inputs_words[var] * WORD_BITS) - 1 + term_min = var_min * coeff + term_max = var_max * coeff + if term_min > term_max: + term_min, term_max = term_max, term_min + min_value += term_min + max_value += term_max + self.min_value = min_value + self.max_value = max_value + self.is_signed = min_value < 0 + + _EvalOpLHS = TypeVar("_EvalOpLHS", int, "EvalOp[Any, Any]") _EvalOpRHS = TypeVar("_EvalOpRHS", int, "EvalOp[Any, Any]") @plain_data(frozen=True, unsafe_hash=True) -class EvalOp(Generic[_EvalOpLHS, _EvalOpRHS]): +class EvalOp(Generic[_EvalOpLHS, _EvalOpRHS], metaclass=ABCMeta): __slots__ = "lhs", "rhs", "poly" @property -- 2.30.2