Skip to content

Commit 6f3a3e0

Browse files
roconnor-blockstreamroconnor-blockstream
committed
No bounded arith for UWORDBound.
While the extraUWORDBound computation could technically overflow, it will not overflow under the condition that the CellsBound computaton does not overflow. Because we do check the CellsBound computation for overflow, there is no need to check the UWORDBound computation as well.
1 parent b075e2c commit 6f3a3e0

File tree

1 file changed

+23
-28
lines changed

1 file changed

+23
-28
lines changed

‎C/eval.c‎

Lines changed: 23 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -658,11 +658,10 @@ typedef struct memBound {
658658
* dag_node dag[len] and 'dag' is well-typed with 'type_dag'.
659659
* Postcondition: if the result is 'true'
660660
* then 'max(dag_bound->extraCellsBound[0], dag_bound->extraCellsBound[1]) == SIZE_MAX'.
661-
* or 'dag_bound->extraCellsBound' characterizes the number of cells needed during evaluation of 'dag';
662-
* 'max(dag_bound->extraUWORDBound[0], dag_bound->extraUWORDBound[1]) == SIZE_MAX'.
663-
* or 'dag_bound->extraUWORDBound' characterizes the number of UWORDs needed
664-
* for the frames allocated during evaluation of 'dag';
665-
* 'dag_bound->extraFrameBound[0]' bounds the the number of stack frames needed during execution of 'dag';
661+
* or 'dag_bound->extraCellsBound' characterizes the number of cells needed during evaluation of 'dag'
662+
* and 'dag_bound->extraUWORDBound' characterizes the number of UWORDs needed
663+
* for the frames allocated during evaluation of 'dag'
664+
* and 'dag_bound->extraFrameBound[0]' bounds the the number of stack frames needed during execution of 'dag';
666665
*/
667666
static bool computeEvalTCOBound(memBound *dag_bound, const dag_node* dag, const type* type_dag, const size_t len) {
668667
static_assert(DAG_LEN_MAX <= SIZE_MAX / sizeof(memBound), "bound array too large.");
@@ -699,23 +698,21 @@ static bool computeEvalTCOBound(memBound *dag_bound, const dag_node* dag, const
699698
/* 'BITSIZE(WORD256 * A)' or 'BITSIZE(B * C)' has exceeded our limits. */
700699
bound[i].extraCellsBound[0] = SIZE_MAX;
701700
bound[i].extraCellsBound[1] = SIZE_MAX;
702-
bound[i].extraUWORDBound[0] = SIZE_MAX;
703-
bound[i].extraUWORDBound[1] = SIZE_MAX;
704701
} else {
705702
bound[i].extraCellsBound[1] = type_dag[DISCONNECT_W256A(dag, type_dag, i)].bitSize;
706703
bound[i].extraCellsBound[0] = max(
707704
bounded_add( type_dag[DISCONNECT_BC(dag, type_dag, i)].bitSize
708705
, max( bounded_add(bound[i].extraCellsBound[1], bound[dag[i].child[0]].extraCellsBound[1])
709706
, max(bound[dag[i].child[0]].extraCellsBound[0], bound[dag[i].child[1]].extraCellsBound[1]))),
710707
bound[dag[i].child[1]].extraCellsBound[0]);
711-
bound[i].extraUWORDBound[1] = ROUND_UWORD(type_dag[DISCONNECT_W256A(dag, type_dag, i)].bitSize);
712-
bound[i].extraUWORDBound[0] = max(
713-
bounded_add(
714-
ROUND_UWORD(type_dag[DISCONNECT_BC(dag, type_dag, i)].bitSize),
715-
max( bounded_add(bound[i].extraUWORDBound[1], bound[dag[i].child[0]].extraUWORDBound[1])
716-
, max(bound[dag[i].child[0]].extraUWORDBound[0], bound[dag[i].child[1]].extraUWORDBound[1]))),
717-
bound[dag[i].child[1]].extraUWORDBound[0]);
718708
}
709+
bound[i].extraUWORDBound[1] = ROUND_UWORD(type_dag[DISCONNECT_W256A(dag, type_dag, i)].bitSize);
710+
bound[i].extraUWORDBound[0] = max(
711+
ROUND_UWORD(type_dag[DISCONNECT_BC(dag, type_dag, i)].bitSize) +
712+
max( bound[i].extraUWORDBound[1] + bound[dag[i].child[0]].extraUWORDBound[1]
713+
, max(bound[dag[i].child[0]].extraUWORDBound[0], bound[dag[i].child[1]].extraUWORDBound[1])),
714+
bound[dag[i].child[1]].extraUWORDBound[0]);
715+
719716
bound[i].extraFrameBound[1] = max( bound[dag[i].child[0]].extraFrameBound[1] + 1
720717
, bound[dag[i].child[1]].extraFrameBound[1]);
721718
bound[i].extraFrameBound[0] = bound[i].extraFrameBound[1] + 1;
@@ -725,22 +722,21 @@ static bool computeEvalTCOBound(memBound *dag_bound, const dag_node* dag, const
725722
/* 'BITSIZE(B)' has exceeded our limits. */
726723
bound[i].extraCellsBound[0] = SIZE_MAX;
727724
bound[i].extraCellsBound[1] = SIZE_MAX;
728-
bound[i].extraUWORDBound[0] = SIZE_MAX;
729-
bound[i].extraUWORDBound[1] = SIZE_MAX;
730725
} else {
731-
size_t scratch = type_dag[COMP_B(dag, type_dag, i)].bitSize;
732-
bound[i].extraCellsBound[0] = max( bounded_add( scratch
726+
bound[i].extraCellsBound[0] = max( bounded_add( type_dag[COMP_B(dag, type_dag, i)].bitSize
733727
, max( bound[dag[i].child[0]].extraCellsBound[0]
734728
, bound[dag[i].child[1]].extraCellsBound[1] ))
735729
, bound[dag[i].child[1]].extraCellsBound[0] );
736-
bound[i].extraCellsBound[1] = bounded_add(scratch, bound[dag[i].child[0]].extraCellsBound[1]);
737-
scratch = ROUND_UWORD(scratch);
738-
bound[i].extraUWORDBound[0] = max( bounded_add( scratch
739-
, max( bound[dag[i].child[0]].extraUWORDBound[0]
740-
, bound[dag[i].child[1]].extraUWORDBound[1] ))
741-
, bound[dag[i].child[1]].extraUWORDBound[0] );
742-
bound[i].extraUWORDBound[1] = bounded_add(scratch, bound[dag[i].child[0]].extraUWORDBound[1]);
730+
bound[i].extraCellsBound[1] = bounded_add( type_dag[COMP_B(dag, type_dag, i)].bitSize
731+
, bound[dag[i].child[0]].extraCellsBound[1] );
743732
}
733+
bound[i].extraUWORDBound[0] = max( ROUND_UWORD(type_dag[COMP_B(dag, type_dag, i)].bitSize) +
734+
max( bound[dag[i].child[0]].extraUWORDBound[0]
735+
, bound[dag[i].child[1]].extraUWORDBound[1] )
736+
, bound[dag[i].child[1]].extraUWORDBound[0] );
737+
bound[i].extraUWORDBound[1] = ROUND_UWORD(type_dag[COMP_B(dag, type_dag, i)].bitSize)
738+
+ bound[dag[i].child[0]].extraUWORDBound[1];
739+
744740
bound[i].extraFrameBound[0] = max( bound[dag[i].child[0]].extraFrameBound[0]
745741
, bound[dag[i].child[1]].extraFrameBound[1] )
746742
+ 1;
@@ -827,9 +823,8 @@ bool evalTCOExpression( bool *evalSuccess, flags_type anti_dos_checks, UWORD* ou
827823
const size_t cellsBound = bounded_add( bounded_add(inputSize, outputSize)
828824
, max(bound.extraCellsBound[0], bound.extraCellsBound[1])
829825
);
830-
const size_t UWORDBound = bounded_add( bounded_add(ROUND_UWORD(inputSize), ROUND_UWORD(outputSize))
831-
, max(bound.extraUWORDBound[0], bound.extraUWORDBound[1])
832-
);
826+
const size_t UWORDBound = ROUND_UWORD(inputSize) + ROUND_UWORD(outputSize)
827+
+ max(bound.extraUWORDBound[0], bound.extraUWORDBound[1]);
833828
const size_t frameBound = bound.extraFrameBound[0] + 2; /* add the initial input and output frames to the count. */
834829

835830
static_assert(CELLS_MAX < SIZE_MAX, "CELLS_MAX is too large.");

0 commit comments

Comments
 (0)