Re: [PATCH v2 4/6] dtc: Add support for signed operations

[David Gibson <david-xT8FGy+AXnRB3Ne2BGzF6laj5H9X9Tb+@public.gmane.org>]

[-- Attachment #1: Type: text/plain, Size: 7807 bytes --]

On Tue, Jul 14, 2020 at 04:45:40PM +0100, Andrei Ziureaev wrote:
> Add support for signed operations, including division, modulo, right
> shift and comparisons. Signed values are "created" by the negation and
> subtraction operators and preserved by other operators as long as the
> value stays negative. Therefore "negative" and "signed" are the same
> thing in this case. Bitwise operators always return unsigned values.
> 
> This is useful for validation with dt-schema, which uses
> arbitrary-precision arithmetic and needs explicit information about the
> sign.
> 
> The TYPE_SIGNED marker can be used by yaml and dts emitters and, if a
> plugin interface is added, by plugins.
> 
> Signed-off-by: Andrei Ziureaev <andrei.ziureaev-5wv7dgnIgG8@public.gmane.org>

Nack to this approach.

I'm pretty inclined to think that having signed arithmetic in dtc is
overkill to begin with.  But even if I'm convinced that we do need it,
then having the operator itself change the type is a really bad idea.


> ---
>  dtc-parser.y                | 81 ++++++++++++++++++++++++++++++++-----
>  dtc.h                       |  2 +
>  tests/integer-expressions.c |  8 ++++
>  3 files changed, 81 insertions(+), 10 deletions(-)
> 
> diff --git a/dtc-parser.y b/dtc-parser.y
> index 3bc1aca..a7c1777 100644
> --- a/dtc-parser.y
> +++ b/dtc-parser.y
> @@ -381,6 +381,8 @@ arrayprefix:
>  		}
>  	| arrayprefix integer_prim
>  		{
> +			struct data data = $1.data;
> +
>  			if ($1.bits < 64) {
>  				uint64_t mask = (1ULL << $1.bits) - 1;
>  				/*
> @@ -396,7 +398,10 @@ arrayprefix:
>  					      " %d-bit array element", $1.bits);
>  			}
>  
> -			$$.data = data_append_integer($1.data, $2.ull, $1.bits);
> +			if ($2.is_negative)
> +				data = data_add_marker(data, TYPE_SIGNED, NULL);
> +
> +			$$.data = data_append_integer(data, $2.ull, $1.bits);
>  		}
>  	| arrayprefix dt_ref
>  		{
> @@ -492,19 +497,31 @@ integer_rela:
>  	  integer_shift
>  	| integer_rela '<' integer_shift
>  		{
> -			$$ = (struct integer){ $1.ull < $3.ull };
> +			if ($1.is_negative || $3.is_negative)
> +				$$ = (struct integer){ (int64_t)$1.ull < (int64_t)$3.ull };
> +			else
> +				$$ = (struct integer){ $1.ull < $3.ull };
>  		}
>  	| integer_rela '>' integer_shift
>  		{
> -			$$ = (struct integer){ $1.ull > $3.ull };
> +			if ($1.is_negative || $3.is_negative)
> +				$$ = (struct integer){ (int64_t)$1.ull > (int64_t)$3.ull };
> +			else
> +				$$ = (struct integer){ $1.ull > $3.ull };
>  		}
>  	| integer_rela DT_LE integer_shift
>  		{
> -			$$ = (struct integer){ $1.ull <= $3.ull };
> +			if ($1.is_negative || $3.is_negative)
> +				$$ = (struct integer){ (int64_t)$1.ull <= (int64_t)$3.ull };
> +			else
> +				$$ = (struct integer){ $1.ull <= $3.ull };
>  		}
>  	| integer_rela DT_GE integer_shift
>  		{
> -			$$ = (struct integer){ $1.ull >= $3.ull };
> +			if ($1.is_negative || $3.is_negative)
> +				$$ = (struct integer){ (int64_t)$1.ull >= (int64_t)$3.ull };
> +			else
> +				$$ = (struct integer){ $1.ull >= $3.ull };
>  		}
>  	;
>  
> @@ -515,7 +532,13 @@ integer_shift:
>  		}
>  	| integer_shift DT_RSHIFT integer_add
>  		{
> -			$$ = (struct integer){ ($3.ull < 64) ? ($1.ull >> $3.ull) : 0 };
> +			if ($3.ull < 64)
> +				if ($1.is_negative)
> +					$$ = (struct integer){ (int64_t)$1.ull >> $3.ull };
> +				else
> +					$$ = (struct integer){ $1.ull >> $3.ull };
> +			else
> +				$$ = (struct integer){ $1.is_negative ? ~0ULL : 0 };
>  		}
>  	| integer_add
>  	;
> @@ -524,10 +547,20 @@ integer_add:
>  	  integer_add '+' integer_mul
>  		{
>  			$$ = (struct integer){ $1.ull + $3.ull };
> +
> +			if ($1.is_negative == $3.is_negative)
> +				$$.is_negative = $1.is_negative;
> +			else
> +				$$.is_negative = $1.ull < -$3.ull;
>  		}
>  	| integer_add '-' integer_mul
>  		{
>  			$$ = (struct integer){ $1.ull - $3.ull };
> +
> +			if ($1.is_negative != $3.is_negative)
> +				$$.is_negative = $1.is_negative;
> +			else
> +				$$.is_negative = $1.ull < $3.ull;
>  		}
>  	| integer_mul
>  	;
> @@ -535,12 +568,29 @@ integer_add:
>  integer_mul:
>  	  integer_mul '*' integer_unary
>  		{
> -			$$ = (struct integer){ $1.ull * $3.ull };
> +			/* For our purpose, signed multiplication is the same as
> +			 * unsigned multiplication */
> +			$$ = (struct integer){
> +				$1.ull * $3.ull,
> +				$1.is_negative != $3.is_negative
> +			};
>  		}
>  	| integer_mul '/' integer_unary
>  		{
>  			if ($3.ull != 0) {
> -				$$ = (struct integer){ $1.ull / $3.ull };
> +				if ($1.is_negative || $3.is_negative) {
> +					/* Prevent UB in signed division */
> +					if (($1.ull == (1ULL << 63)) && ($3.ull == ~0ULL))
> +						$$ = (struct integer){ $1.ull };
> +					else
> +						$$ = (struct integer){
> +							(int64_t)$1.ull / (int64_t)$3.ull
> +						};
> +
> +					$$.is_negative = $1.is_negative != $3.is_negative;
> +				} else {
> +					$$ = (struct integer){ $1.ull / $3.ull };
> +				}
>  			} else {
>  				ERROR(&@$, "Division by zero");
>  				$$ = (struct integer){ 0 };
> @@ -549,7 +599,18 @@ integer_mul:
>  	| integer_mul '%' integer_unary
>  		{
>  			if ($3.ull != 0) {
> -			$$ = (struct integer){ $1.ull % $3.ull };
> +				if ($1.is_negative || $3.is_negative) {
> +					if (($1.ull == (1ULL << 63)) && ($3.ull == ~0ULL))
> +						$$ = (struct integer){ 0 };
> +					else
> +						$$ = (struct integer){
> +							(int64_t)$1.ull % (int64_t)$3.ull
> +						};
> +
> +					$$.is_negative = $1.is_negative;
> +				} else {
> +					$$ = (struct integer){ $1.ull % $3.ull };
> +				}
>  			} else {
>  				ERROR(&@$, "Division by zero");
>  				$$ = (struct integer){ 0 };
> @@ -562,7 +623,7 @@ integer_unary:
>  	  integer_prim
>  	| '-' integer_unary
>  		{
> -			$$ = (struct integer){ -$2.ull };
> +			$$ = (struct integer){ -$2.ull, !$2.is_negative };
>  		}
>  	| '~' integer_unary
>  		{
> diff --git a/dtc.h b/dtc.h
> index ccfe689..a502bef 100644
> --- a/dtc.h
> +++ b/dtc.h
> @@ -95,6 +95,7 @@ enum markertype {
>  	REF_PHANDLE,
>  	REF_PATH,
>  	LABEL,
> +	TYPE_SIGNED,
>  	TYPE_UINT8,
>  	TYPE_UINT16,
>  	TYPE_UINT32,
> @@ -119,6 +120,7 @@ struct data {
>  
>  struct integer {
>  	uint64_t ull;
> +	bool is_negative;
>  };
>  
>  #define empty_data ((struct data){ 0 /* all .members = 0 or NULL */ })
> diff --git a/tests/integer-expressions.c b/tests/integer-expressions.c
> index 6f33d81..041efb0 100644
> --- a/tests/integer-expressions.c
> +++ b/tests/integer-expressions.c
> @@ -28,15 +28,22 @@ static struct test_expr {
>  	TE(2*3),
>  	TE(4/2),
>  	TE(10/3),
> +	TE(-10/3),
>  	TE(19%4),
> +	TE(-19%4),
>  	TE(1 << 13),
>  	TE(0x1000 >> 4),
> +	TE(-0x1000 >> 4),
>  	TE(3*2+1), TE(3*(2+1)),
>  	TE(1+2*3), TE((1+2)*3),
>  	TE(1 < 2), TE(2 < 1), TE(1 < 1),
>  	TE(1 <= 2), TE(2 <= 1), TE(1 <= 1),
>  	TE(1 > 2), TE(2 > 1), TE(1 > 1),
>  	TE(1 >= 2), TE(2 >= 1), TE(1 >= 1),
> +	TE(-1 < 1), TE(1 < -1), TE(-1 < -1),
> +	TE(-1 <= 1), TE(1 <= -1), TE(-1 <= -1),
> +	TE(-1 > 1), TE(1 > -1), TE(-1 > -1),
> +	TE(-1 >= 1), TE(1 >= -1), TE(-1 >= -1),
>  	TE(1 == 1), TE(1 == 2),
>  	TE(1 != 1), TE(1 != 2),
>  	TE(0xabcdabcd & 0xffff0000),
> @@ -50,6 +57,7 @@ static struct test_expr {
>  	TE(0 ? 17 : 39), TE(1 ? 17 : 39), TE(17 ? 0xdeadbeef : 0xabcd1234),
>  	TE(11 * 257 * 1321517ULL),
>  	TE(123456790 - 4/2 + 17%4),
> +	TE(-123456790 - -4/-2 + -17%-4),
>  };
>  
>  #define ARRAY_SIZE(x)	(sizeof(x) / sizeof((x)[0]))

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]