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

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

[Andrei Ziureaev]

Following the discussion on v1, I decided to add proper support for all
signed operations.

The first two patches can be useful on their own.

Patches 3/6 to 6/6 add support for signed operations and sign
preservation in high-level output formats.

All operators are supported, which means some of them will behave
differently with negative values, namely: /, %, >>, <, <=, >, >=. I
haven't found any existing dts files using these operators with negative
values.

There is no explicit signed type in the dts format, but the idea is to
infer the sign as intuitively as possible: negative values are signed,
positive values are unsigned. Zero can be either, so the output side
checks for that. I haven't given much thought to overflows, but they
happen to be handled well, I think (at least UB in C is prevented).

This change allows us to validate dts files that contain negative
values. One could argue that (-1 == 0xffffffff), so there's no point in
doing this, but dt-schema is written in Python 3, which uses
arbitrary-precision arithmetic and doesn't have the traditional
overflowing types. This makes it hard to solve this problem in dt-schema
(especially checking if a signed value is within a range, I think).

Thanks,
Andrei.

Changes in v2:
- avoid UB when shifting
- add a bytestring type
- add support for all the operators
- use TYPE_SIGNED, instead of TYPE_NEGATIVE
- use macros on the output side
- add more tests

Andrei Ziureaev (6):
  dtc: Avoid UB when shifting
  dtc: Add bytestring type
  dtc: Turn 'uint64_t integer' into a struct
  dtc: Add support for signed operations
  dtc: Preserve negative integers in yaml and dts
  dtc: Add sign preservation and operation tests

 dtc-lexer.l                     |  10 +-
 dtc-parser.y                    | 190 ++++++++++++++++++++++++++------
 dtc.h                           |  14 +++
 tests/integer-expressions.c     |   8 ++
 tests/operations-expected.dts   |  31 ++++++
 tests/operations.dt.yaml        |  29 +++++
 tests/operations.dts            |  38 +++++++
 tests/run_tests.sh              |  13 ++-
 tests/sign-preservation.dt.yaml |  23 ++++
 tests/sign-preservation.dts     |  31 ++++++
 tests/type-preservation.dt.yaml |   2 +
 tests/type-preservation.dts     |   6 +-
 treesource.c                    |  47 +++++---
 yamltree.c                      |  27 ++---
 14 files changed, 399 insertions(+), 70 deletions(-)
 create mode 100644 tests/operations-expected.dts
 create mode 100644 tests/operations.dt.yaml
 create mode 100644 tests/operations.dts
 create mode 100644 tests/sign-preservation.dt.yaml
 create mode 100644 tests/sign-preservation.dts

-- 
2.17.1

[PATCH v2 1/6] dtc: Avoid UB when shifting

[Andrei Ziureaev]

Prevent undefined behavior when shifting by a number that's bigger than
or equal to the width of the first operand.

Signed-off-by: Andrei Ziureaev <andrei.ziureaev-5wv7dgnIgG8@public.gmane.org>
---
 dtc-parser.y | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/dtc-parser.y b/dtc-parser.y
index 40dcf4f..a0316a3 100644
--- a/dtc-parser.y
+++ b/dtc-parser.y
@@ -476,8 +476,8 @@ integer_rela:
 	;
 
 integer_shift:
-	  integer_shift DT_LSHIFT integer_add { $$ = $1 << $3; }
-	| integer_shift DT_RSHIFT integer_add { $$ = $1 >> $3; }
+	  integer_shift DT_LSHIFT integer_add { $$ = ($3 < 64) ? ($1 << $3) : 0; }
+	| integer_shift DT_RSHIFT integer_add { $$ = ($3 < 64) ? ($1 >> $3) : 0; }
 	| integer_add
 	;
 
-- 
2.17.1

[PATCH v2 2/6] dtc: Add bytestring type

[Andrei Ziureaev]

Differentiate between the /bits/ 8 <...> and [...] formats in dts output
by adding a TYPE_BYTESTRING type. This could be useful if we later end
up exporting the internal livetree to plugins.

Signed-off-by: Andrei Ziureaev <andrei.ziureaev-5wv7dgnIgG8@public.gmane.org>
---
 dtc-parser.y                    |  2 +-
 dtc.h                           |  1 +
 tests/type-preservation.dt.yaml |  2 ++
 tests/type-preservation.dts     |  6 ++++--
 treesource.c                    | 24 +++++++++++++++---------
 5 files changed, 23 insertions(+), 12 deletions(-)

diff --git a/dtc-parser.y b/dtc-parser.y
index a0316a3..c8c1875 100644
--- a/dtc-parser.y
+++ b/dtc-parser.y
@@ -520,7 +520,7 @@ integer_unary:
 bytestring:
 	  /* empty */
 		{
-			$$ = data_add_marker(empty_data, TYPE_UINT8, NULL);
+			$$ = data_add_marker(empty_data, TYPE_BYTESTRING, NULL);
 		}
 	| bytestring DT_BYTE
 		{
diff --git a/dtc.h b/dtc.h
index a08f415..e3225ab 100644
--- a/dtc.h
+++ b/dtc.h
@@ -100,6 +100,7 @@ enum markertype {
 	TYPE_UINT32,
 	TYPE_UINT64,
 	TYPE_STRING,
+	TYPE_BYTESTRING,
 };
 extern const char *markername(enum markertype markertype);
 
diff --git a/tests/type-preservation.dt.yaml b/tests/type-preservation.dt.yaml
index ee8cfde..98f05df 100644
--- a/tests/type-preservation.dt.yaml
+++ b/tests/type-preservation.dt.yaml
@@ -5,6 +5,8 @@
     compatible: ["subnode1"]
     reg: [[0x1]]
     int-array: [[0x0, 0x1], [0x2, 0x3]]
+    byte: [!u8 [0x56]]
+    bytestring: [!u8 [0x0, 0x12, 0x34, 0x56]]
     int8: [!u8 [0x56]]
     int8-array: [!u8 [0x0, 0x12, 0x34, 0x56]]
     int16: [!u16 [0x3210]]
diff --git a/tests/type-preservation.dts b/tests/type-preservation.dts
index 3e380ba..24c9eeb 100644
--- a/tests/type-preservation.dts
+++ b/tests/type-preservation.dts
@@ -8,8 +8,10 @@
 		prop_label: compatible = value_label: "subnode1";
 		reg = <0x01>;
 		int-array = <0x00 0x01>, int_value_label: <0x02 0x03>;
-		int8 = [56];
-		int8-array = [00 12 34 56] label:;
+		byte = [56];
+		bytestring = [00 12 34 56] label:;
+		int8 = /bits/ 8 <0x56>;
+		int8-array = /bits/ 8 <0x00 0x12 0x34 0x56> int8_label:;
 		int16 = /bits/ 16 <0x3210>;
 		int16-array = /bits/ 16 <0x1234 0x5678 0x90ab 0xcdef>;
 		int16-matrix = /bits/ 16 <0x1234 0x5678>, <0x90ab 0xcdef>;
diff --git a/treesource.c b/treesource.c
index 061ba8c..322d9e7 100644
--- a/treesource.c
+++ b/treesource.c
@@ -99,7 +99,8 @@ static void write_propval_string(FILE *f, const char *s, size_t len)
 	fprintf(f, "\"");
 }
 
-static void write_propval_int(FILE *f, const char *p, size_t len, size_t width)
+static void write_propval_int(FILE *f, struct marker *markers,
+			      const char *p, size_t len, size_t width)
 {
 	const char *end = p + len;
 	assert(len % width == 0);
@@ -107,7 +108,10 @@ static void write_propval_int(FILE *f, const char *p, size_t len, size_t width)
 	for (; p < end; p += width) {
 		switch (width) {
 		case 1:
-			fprintf(f, "%02"PRIx8, *(const uint8_t*)p);
+			if (markers->type == TYPE_BYTESTRING)
+				fprintf(f, "%02"PRIx8, *(const uint8_t*)p);
+			else
+				fprintf(f, "0x%02"PRIx8, *(const uint8_t*)p);
 			break;
 		case 2:
 			fprintf(f, "0x%02"PRIx16, dtb_ld16(p));
@@ -146,18 +150,20 @@ size_t type_marker_length(struct marker *m)
 }
 
 static const char *delim_start[] = {
-	[TYPE_UINT8] = "[",
+	[TYPE_UINT8] = "/bits/ 8 <",
 	[TYPE_UINT16] = "/bits/ 16 <",
 	[TYPE_UINT32] = "<",
 	[TYPE_UINT64] = "/bits/ 64 <",
 	[TYPE_STRING] = "",
+	[TYPE_BYTESTRING] = "[",
 };
 static const char *delim_end[] = {
-	[TYPE_UINT8] = "]",
+	[TYPE_UINT8] = ">",
 	[TYPE_UINT16] = ">",
 	[TYPE_UINT32] = ">",
 	[TYPE_UINT64] = ">",
 	[TYPE_STRING] = "",
+	[TYPE_BYTESTRING] = "]",
 };
 
 static enum markertype guess_value_type(struct property *prop)
@@ -190,7 +196,7 @@ static enum markertype guess_value_type(struct property *prop)
 		return TYPE_UINT32;
 	}
 
-	return TYPE_UINT8;
+	return TYPE_BYTESTRING;
 }
 
 static void write_propval(FILE *f, struct property *prop)
@@ -245,19 +251,19 @@ static void write_propval(FILE *f, struct property *prop)
 
 		switch(emit_type) {
 		case TYPE_UINT16:
-			write_propval_int(f, p, chunk_len, 2);
+			write_propval_int(f, m, p, chunk_len, 2);
 			break;
 		case TYPE_UINT32:
-			write_propval_int(f, p, chunk_len, 4);
+			write_propval_int(f, m, p, chunk_len, 4);
 			break;
 		case TYPE_UINT64:
-			write_propval_int(f, p, chunk_len, 8);
+			write_propval_int(f, m, p, chunk_len, 8);
 			break;
 		case TYPE_STRING:
 			write_propval_string(f, p, chunk_len);
 			break;
 		default:
-			write_propval_int(f, p, chunk_len, 1);
+			write_propval_int(f, m, p, chunk_len, 1);
 		}
 
 		if (chunk_len == data_len) {
-- 
2.17.1

[PATCH v2 3/6] dtc: Turn 'uint64_t integer' into a struct

[Andrei Ziureaev]

This allows adding support for signed operations and preserving negative
integers in yaml and dts output.

Signed-off-by: Andrei Ziureaev <andrei.ziureaev-5wv7dgnIgG8@public.gmane.org>
---
 dtc-lexer.l  |  10 ++--
 dtc-parser.y | 127 +++++++++++++++++++++++++++++++++++++--------------
 dtc.h        |   3 ++
 3 files changed, 102 insertions(+), 38 deletions(-)

diff --git a/dtc-lexer.l b/dtc-lexer.l
index b3b7270..037a2ab 100644
--- a/dtc-lexer.l
+++ b/dtc-lexer.l
@@ -156,7 +156,9 @@ static void PRINTF(1, 2) lexical_error(const char *fmt, ...);
 			DPRINT("Integer Literal: '%s'\n", yytext);
 
 			errno = 0;
-			yylval.integer = strtoull(yytext, &e, 0);
+			yylval.integer = (struct integer){
+				strtoull(yytext, &e, 0)
+			};
 
 			if (*e && e[strspn(e, "UL")]) {
 				lexical_error("Bad integer literal '%s'",
@@ -180,9 +182,11 @@ static void PRINTF(1, 2) lexical_error(const char *fmt, ...);
 			d = data_copy_escape_string(yytext+1, yyleng-2);
 			if (d.len == 1) {
 				lexical_error("Empty character literal");
-				yylval.integer = 0;
+				yylval.integer = (struct integer){ 0 };
 			} else {
-				yylval.integer = (unsigned char)d.val[0];
+				yylval.integer = (struct integer){
+					(unsigned char)d.val[0]
+				};
 
 				if (d.len > 2)
 					lexical_error("Character literal has %d"
diff --git a/dtc-parser.y b/dtc-parser.y
index c8c1875..3bc1aca 100644
--- a/dtc-parser.y
+++ b/dtc-parser.y
@@ -41,7 +41,7 @@ extern bool treesource_error;
 	struct node *node;
 	struct node *nodelist;
 	struct reserve_info *re;
-	uint64_t integer;
+	struct integer integer;
 	unsigned int flags;
 }
 
@@ -140,7 +140,7 @@ memreserves:
 memreserve:
 	  DT_MEMRESERVE integer_prim integer_prim ';'
 		{
-			$$ = build_reserve_entry($2, $3);
+			$$ = build_reserve_entry($2.ull, $3.ull);
 		}
 	| DT_LABEL memreserve
 		{
@@ -310,13 +310,13 @@ propdata:
 			FILE *f = srcfile_relative_open($4.val, NULL);
 			struct data d;
 
-			if ($6 != 0)
-				if (fseek(f, $6, SEEK_SET) != 0)
+			if ($6.ull != 0)
+				if (fseek(f, $6.ull, SEEK_SET) != 0)
 					die("Couldn't seek to offset %llu in \"%s\": %s",
-					    (unsigned long long)$6, $4.val,
+					    (unsigned long long)$6.ull, $4.val,
 					    strerror(errno));
 
-			d = data_copy_file(f, $8);
+			d = data_copy_file(f, $8.ull);
 
 			$$ = data_merge($1, d);
 			fclose(f);
@@ -358,7 +358,7 @@ arrayprefix:
 			unsigned long long bits;
 			enum markertype type = TYPE_UINT32;
 
-			bits = $2;
+			bits = $2.ull;
 
 			switch (bits) {
 			case 8: type = TYPE_UINT8; break;
@@ -391,12 +391,12 @@ arrayprefix:
 				 * within the mask to one (i.e. | in the
 				 * mask), all bits are one.
 				 */
-				if (($2 > mask) && (($2 | mask) != -1ULL))
+				if (($2.ull > mask) && (($2.ull | mask) != -1ULL))
 					ERROR(&@2, "Value out of range for"
 					      " %d-bit array element", $1.bits);
 			}
 
-			$$.data = data_append_integer($1.data, $2, $1.bits);
+			$$.data = data_append_integer($1.data, $2.ull, $1.bits);
 		}
 	| arrayprefix dt_ref
 		{
@@ -433,78 +433,126 @@ integer_expr:
 
 integer_trinary:
 	  integer_or
-	| integer_or '?' integer_expr ':' integer_trinary { $$ = $1 ? $3 : $5; }
+	| integer_or '?' integer_expr ':' integer_trinary { $$ = $1.ull ? $3 : $5; }
 	;
 
 integer_or:
 	  integer_and
-	| integer_or DT_OR integer_and { $$ = $1 || $3; }
+	| integer_or DT_OR integer_and
+		{
+			$$ = (struct integer){ $1.ull || $3.ull };
+		}
 	;
 
 integer_and:
 	  integer_bitor
-	| integer_and DT_AND integer_bitor { $$ = $1 && $3; }
+	| integer_and DT_AND integer_bitor
+		{
+			$$ = (struct integer){ $1.ull && $3.ull };
+		}
 	;
 
 integer_bitor:
 	  integer_bitxor
-	| integer_bitor '|' integer_bitxor { $$ = $1 | $3; }
+	| integer_bitor '|' integer_bitxor
+		{
+			$$ = (struct integer){ $1.ull | $3.ull };
+		}
 	;
 
 integer_bitxor:
 	  integer_bitand
-	| integer_bitxor '^' integer_bitand { $$ = $1 ^ $3; }
+	| integer_bitxor '^' integer_bitand
+		{
+			$$ = (struct integer){ $1.ull ^ $3.ull };
+		}
 	;
 
 integer_bitand:
 	  integer_eq
-	| integer_bitand '&' integer_eq { $$ = $1 & $3; }
+	| integer_bitand '&' integer_eq
+		{
+			$$ = (struct integer){ $1.ull & $3.ull };
+		}
 	;
 
 integer_eq:
 	  integer_rela
-	| integer_eq DT_EQ integer_rela { $$ = $1 == $3; }
-	| integer_eq DT_NE integer_rela { $$ = $1 != $3; }
+	| integer_eq DT_EQ integer_rela
+		{
+			$$ = (struct integer){ $1.ull == $3.ull };
+		}
+	| integer_eq DT_NE integer_rela
+		{
+			$$ = (struct integer){ $1.ull != $3.ull };
+		}
 	;
 
 integer_rela:
 	  integer_shift
-	| integer_rela '<' integer_shift { $$ = $1 < $3; }
-	| integer_rela '>' integer_shift { $$ = $1 > $3; }
-	| integer_rela DT_LE integer_shift { $$ = $1 <= $3; }
-	| integer_rela DT_GE integer_shift { $$ = $1 >= $3; }
+	| integer_rela '<' integer_shift
+		{
+			$$ = (struct integer){ $1.ull < $3.ull };
+		}
+	| integer_rela '>' integer_shift
+		{
+			$$ = (struct integer){ $1.ull > $3.ull };
+		}
+	| integer_rela DT_LE integer_shift
+		{
+			$$ = (struct integer){ $1.ull <= $3.ull };
+		}
+	| integer_rela DT_GE integer_shift
+		{
+			$$ = (struct integer){ $1.ull >= $3.ull };
+		}
 	;
 
 integer_shift:
-	  integer_shift DT_LSHIFT integer_add { $$ = ($3 < 64) ? ($1 << $3) : 0; }
-	| integer_shift DT_RSHIFT integer_add { $$ = ($3 < 64) ? ($1 >> $3) : 0; }
+	  integer_shift DT_LSHIFT integer_add
+		{
+			$$ = (struct integer){ ($3.ull < 64) ? ($1.ull << $3.ull) : 0 };
+		}
+	| integer_shift DT_RSHIFT integer_add
+		{
+			$$ = (struct integer){ ($3.ull < 64) ? ($1.ull >> $3.ull) : 0 };
+		}
 	| integer_add
 	;
 
 integer_add:
-	  integer_add '+' integer_mul { $$ = $1 + $3; }
-	| integer_add '-' integer_mul { $$ = $1 - $3; }
+	  integer_add '+' integer_mul
+		{
+			$$ = (struct integer){ $1.ull + $3.ull };
+		}
+	| integer_add '-' integer_mul
+		{
+			$$ = (struct integer){ $1.ull - $3.ull };
+		}
 	| integer_mul
 	;
 
 integer_mul:
-	  integer_mul '*' integer_unary { $$ = $1 * $3; }
+	  integer_mul '*' integer_unary
+		{
+			$$ = (struct integer){ $1.ull * $3.ull };
+		}
 	| integer_mul '/' integer_unary
 		{
-			if ($3 != 0) {
-				$$ = $1 / $3;
+			if ($3.ull != 0) {
+				$$ = (struct integer){ $1.ull / $3.ull };
 			} else {
 				ERROR(&@$, "Division by zero");
-				$$ = 0;
+				$$ = (struct integer){ 0 };
 			}
 		}
 	| integer_mul '%' integer_unary
 		{
-			if ($3 != 0) {
-				$$ = $1 % $3;
+			if ($3.ull != 0) {
+			$$ = (struct integer){ $1.ull % $3.ull };
 			} else {
 				ERROR(&@$, "Division by zero");
-				$$ = 0;
+				$$ = (struct integer){ 0 };
 			}
 		}
 	| integer_unary
@@ -512,9 +560,18 @@ integer_mul:
 
 integer_unary:
 	  integer_prim
-	| '-' integer_unary { $$ = -$2; }
-	| '~' integer_unary { $$ = ~$2; }
-	| '!' integer_unary { $$ = !$2; }
+	| '-' integer_unary
+		{
+			$$ = (struct integer){ -$2.ull };
+		}
+	| '~' integer_unary
+		{
+			$$ = (struct integer){ ~$2.ull };
+		}
+	| '!' integer_unary
+		{
+			$$ = (struct integer){ !$2.ull };
+		}
 	;
 
 bytestring:
diff --git a/dtc.h b/dtc.h
index e3225ab..ccfe689 100644
--- a/dtc.h
+++ b/dtc.h
@@ -117,6 +117,9 @@ struct data {
 	struct marker *markers;
 };
 
+struct integer {
+	uint64_t ull;
+};
 
 #define empty_data ((struct data){ 0 /* all .members = 0 or NULL */ })
 
-- 
2.17.1

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

[Andrei Ziureaev]

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>
---
 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]))
-- 
2.17.1

[PATCH v2 5/6] dtc: Preserve negative integers in yaml and dts

[Andrei Ziureaev]

The dts format supports signed integers, but dts to dts and dts to yaml
conversions don't preserve the sign on output. This is a problem for
doing validation with schema that define a signed type.

Preserve the '-' sign in front of negative values in dts and yaml
output.

Signed-off-by: Andrei Ziureaev <andrei.ziureaev-5wv7dgnIgG8@public.gmane.org>
---
 dtc.h        |  8 ++++++++
 treesource.c | 25 ++++++++++++++++++++-----
 yamltree.c   | 27 ++++++++++++++-------------
 3 files changed, 42 insertions(+), 18 deletions(-)

diff --git a/dtc.h b/dtc.h
index a502bef..ba840ef 100644
--- a/dtc.h
+++ b/dtc.h
@@ -131,6 +131,14 @@ struct integer {
 	for_each_marker(m) \
 		if ((m)->type == (t))
 
+static inline bool has_type_at_offset(struct marker *m, enum markertype type, int off)
+{
+	for_each_marker_of_type(m, type)
+		if (m->offset == off)
+			return true;
+	return false;
+}
+
 size_t type_marker_length(struct marker *m);
 
 void data_free(struct data d);
diff --git a/treesource.c b/treesource.c
index 322d9e7..3072bf7 100644
--- a/treesource.c
+++ b/treesource.c
@@ -13,6 +13,14 @@ extern YYLTYPE yylloc;
 struct dt_info *parser_output;
 bool treesource_error;
 
+#define write_int(f, is_sig, val, w) (					\
+{									\
+	if ((is_sig) && (int##w##_t)(val) < 0)				\
+		fprintf(f, "(-0x%02"PRIx##w")", (uint##w##_t)-(val));	\
+	else								\
+		fprintf(f, "0x%02"PRIx##w, val);			\
+})
+
 struct dt_info *dt_from_source(const char *fname)
 {
 	parser_output = NULL;
@@ -102,25 +110,30 @@ static void write_propval_string(FILE *f, const char *s, size_t len)
 static void write_propval_int(FILE *f, struct marker *markers,
 			      const char *p, size_t len, size_t width)
 {
+	int start_offset = markers->offset;
+	const char *start = p;
 	const char *end = p + len;
 	assert(len % width == 0);
 
 	for (; p < end; p += width) {
+		int off = start_offset + (int)(p - start);
+		bool is_sig = has_type_at_offset(markers, TYPE_SIGNED, off);
+
 		switch (width) {
 		case 1:
 			if (markers->type == TYPE_BYTESTRING)
 				fprintf(f, "%02"PRIx8, *(const uint8_t*)p);
 			else
-				fprintf(f, "0x%02"PRIx8, *(const uint8_t*)p);
+				write_int(f, is_sig, *(const uint8_t*)p, 8);
 			break;
 		case 2:
-			fprintf(f, "0x%02"PRIx16, dtb_ld16(p));
+			write_int(f, is_sig, dtb_ld16(p), 16);
 			break;
 		case 4:
-			fprintf(f, "0x%02"PRIx32, dtb_ld32(p));
+			write_int(f, is_sig, dtb_ld32(p), 32);
 			break;
 		case 8:
-			fprintf(f, "0x%02"PRIx64, dtb_ld64(p));
+			write_int(f, is_sig, dtb_ld64(p), 64);
 			break;
 		}
 		if (p + width < end)
@@ -202,6 +215,7 @@ static enum markertype guess_value_type(struct property *prop)
 static void write_propval(FILE *f, struct property *prop)
 {
 	size_t len = prop->val.len;
+	size_t last_type_off = 0;
 	struct marker *m = prop->val.markers;
 	struct marker dummy_marker;
 	enum markertype emit_type = TYPE_NONE;
@@ -237,11 +251,12 @@ static void write_propval(FILE *f, struct property *prop)
 		const char *p = &prop->val.val[m->offset];
 
 		if (has_data_type_information(m)) {
+			last_type_off = m->offset;
 			emit_type = m->type;
 			fprintf(f, " %s", delim_start[emit_type]);
 		} else if (m->type == LABEL)
 			fprintf(f, " %s:", m->ref);
-		else if (m->offset)
+		else if (m->offset != last_type_off)
 			fputc(' ', f);
 
 		if (emit_type == TYPE_NONE) {
diff --git a/yamltree.c b/yamltree.c
index 4e93c12..c1c3710 100644
--- a/yamltree.c
+++ b/yamltree.c
@@ -29,6 +29,14 @@ char *yaml_error_name[] = {
 		    (emitter)->problem, __func__, __LINE__);		\
 })
 
+#define yaml_write_int(buf, is_sig, val, w) (				\
+{									\
+	if ((is_sig) && (int##w##_t)(val) < 0)				\
+		snprintf(buf, 20, "-0x%"PRIx##w, (uint##w##_t)-(val));	\
+	else								\
+		snprintf(buf, 19, "0x%"PRIx##w, val);			\
+})
+
 static void yaml_propval_int(yaml_emitter_t *emitter, struct marker *markers, char *data, int len, int width)
 {
 	yaml_event_t event;
@@ -51,29 +59,22 @@ static void yaml_propval_int(yaml_emitter_t *emitter, struct marker *markers, ch
 
 	for (off = 0; off < len; off += width) {
 		char buf[32];
-		struct marker *m;
 		bool is_phandle = false;
+		bool is_sig = has_type_at_offset(markers, TYPE_SIGNED, start_offset + off);
 
 		switch(width) {
 		case 1:
-			sprintf(buf, "0x%"PRIx8, *(uint8_t*)(data + off));
+			yaml_write_int(buf, is_sig, *(uint8_t*)(data + off), 8);
 			break;
 		case 2:
-			sprintf(buf, "0x%"PRIx16, dtb_ld16(data + off));
+			yaml_write_int(buf, is_sig, dtb_ld16(data + off), 16);
 			break;
 		case 4:
-			sprintf(buf, "0x%"PRIx32, dtb_ld32(data + off));
-			m = markers;
-			is_phandle = false;
-			for_each_marker_of_type(m, REF_PHANDLE) {
-				if (m->offset == (start_offset + off)) {
-					is_phandle = true;
-					break;
-				}
-			}
+			yaml_write_int(buf, is_sig, dtb_ld32(data + off), 32);
+			is_phandle = has_type_at_offset(markers, REF_PHANDLE, start_offset + off);
 			break;
 		case 8:
-			sprintf(buf, "0x%"PRIx64, dtb_ld64(data + off));
+			yaml_write_int(buf, is_sig, dtb_ld64(data + off), 64);
 			break;
 		}
 
-- 
2.17.1

[PATCH v2 6/6] dtc: Add sign preservation and operation tests

[Andrei Ziureaev]

There are two types of tests here:

1. Test whether dts and yaml outputs preserve the signs of integers in
all types

2. Test whether signed operations are performed as expected and whether
the results are formatted correctly

Signed-off-by: Andrei Ziureaev <andrei.ziureaev-5wv7dgnIgG8@public.gmane.org>
---
 tests/operations-expected.dts   | 31 +++++++++++++++++++++++++++
 tests/operations.dt.yaml        | 29 +++++++++++++++++++++++++
 tests/operations.dts            | 38 +++++++++++++++++++++++++++++++++
 tests/run_tests.sh              | 13 ++++++++---
 tests/sign-preservation.dt.yaml | 23 ++++++++++++++++++++
 tests/sign-preservation.dts     | 31 +++++++++++++++++++++++++++
 6 files changed, 162 insertions(+), 3 deletions(-)
 create mode 100644 tests/operations-expected.dts
 create mode 100644 tests/operations.dt.yaml
 create mode 100644 tests/operations.dts
 create mode 100644 tests/sign-preservation.dt.yaml
 create mode 100644 tests/sign-preservation.dts

diff --git a/tests/operations-expected.dts b/tests/operations-expected.dts
new file mode 100644
index 0000000..fde094e
--- /dev/null
+++ b/tests/operations-expected.dts
@@ -0,0 +1,31 @@
+/dts-v1/;
+
+/ {
+	tri = <0x02 (-0x02) (-0x01) 0x01>;
+	or = <0x00 0x01 0x01 0x01 0x00 0x01 0x01 0x01>;
+	and = <0x00 0x00 0x00 0x01 0x00 0x00 0x00 0x01>;
+	bo = <0x03 0xffffffff 0xffffffff 0xffffffff>;
+	bx = <0x03 0xfffffffd 0xffffffff 0x01>;
+	ba = <0x00 0x02 0x00 0xfffffffe>;
+	eq = <0x00 0x00 0x01 0x01>;
+	neq = <0x01 0x01 0x00 0x00>;
+	l = <0x00 0x01 0x00 0x01 0x00>;
+	g = <0x01 0x00 0x01 0x00 0x00>;
+	leq = <0x00 0x01 0x00 0x01 0x01>;
+	geq = <0x01 0x00 0x01 0x00 0x01>;
+	lsh = <0x02 0xfffffffe 0x00 0x00>;
+	rsh = <0x01 0xfffffffe 0xffffffff 0xffffffff 0x00>;
+	add = <0x07 (-0x01) 0x01 (-0x07)>;
+	sub = <0x01 (-0x07) 0x07 (-0x01)>;
+	mul = <0x0c (-0x0c) (-0x0c) 0x0c>;
+	div = <0x01 (-0x01) (-0x01) 0x01 0x00>;
+	mod = <0x01 (-0x01) 0x01 (-0x01) 0x00>;
+	neg = <0x00 0x00 (-0x01) 0x01>;
+	bit-not = <0xffffffff 0xffffffff 0xfffffffe 0x00>;
+	log-not = <0x01 0x01 0x00 0x00>;
+	big-add = <0xffffffff 0xffffffff 0xfffffffe 0xfffffffe (-0x7fffffff)>;
+	big-sub = <0xfffffffe 0x02 0x00>;
+	big-div = /bits/ 64 <(-0x8000000000000000) 0x00 0x00>;
+	big-mod = /bits/ 64 <0x00 0x00>;
+	big-neg = <0x01 0xffffffff (-0x80000000) 0x80000000>;
+};
diff --git a/tests/operations.dt.yaml b/tests/operations.dt.yaml
new file mode 100644
index 0000000..0a5b712
--- /dev/null
+++ b/tests/operations.dt.yaml
@@ -0,0 +1,29 @@
+---
+- tri: [[0x2, -0x2, -0x1, 0x1]]
+  or: [[0x0, 0x1, 0x1, 0x1, 0x0, 0x1, 0x1, 0x1]]
+  and: [[0x0, 0x0, 0x0, 0x1, 0x0, 0x0, 0x0, 0x1]]
+  bo: [[0x3, 0xffffffff, 0xffffffff, 0xffffffff]]
+  bx: [[0x3, 0xfffffffd, 0xffffffff, 0x1]]
+  ba: [[0x0, 0x2, 0x0, 0xfffffffe]]
+  eq: [[0x0, 0x0, 0x1, 0x1]]
+  neq: [[0x1, 0x1, 0x0, 0x0]]
+  l: [[0x0, 0x1, 0x0, 0x1, 0x0]]
+  g: [[0x1, 0x0, 0x1, 0x0, 0x0]]
+  leq: [[0x0, 0x1, 0x0, 0x1, 0x1]]
+  geq: [[0x1, 0x0, 0x1, 0x0, 0x1]]
+  lsh: [[0x2, 0xfffffffe, 0x0, 0x0]]
+  rsh: [[0x1, 0xfffffffe, 0xffffffff, 0xffffffff, 0x0]]
+  add: [[0x7, -0x1, 0x1, -0x7]]
+  sub: [[0x1, -0x7, 0x7, -0x1]]
+  mul: [[0xc, -0xc, -0xc, 0xc]]
+  div: [[0x1, -0x1, -0x1, 0x1, 0x0]]
+  mod: [[0x1, -0x1, 0x1, -0x1, 0x0]]
+  neg: [[0x0, 0x0, -0x1, 0x1]]
+  bit-not: [[0xffffffff, 0xffffffff, 0xfffffffe, 0x0]]
+  log-not: [[0x1, 0x1, 0x0, 0x0]]
+  big-add: [[0xffffffff, 0xffffffff, 0xfffffffe, 0xfffffffe, -0x7fffffff]]
+  big-sub: [[0xfffffffe, 0x2, 0x0]]
+  big-div: [!u64 [-0x8000000000000000, 0x0, 0x0]]
+  big-mod: [!u64 [0x0, 0x0]]
+  big-neg: [[0x1, 0xffffffff, -0x80000000, 0x80000000]]
+...
diff --git a/tests/operations.dts b/tests/operations.dts
new file mode 100644
index 0000000..4af7154
--- /dev/null
+++ b/tests/operations.dts
@@ -0,0 +1,38 @@
+/dts-v1/;
+
+/ {
+	tri = <(0 ? 1 : 2) (-0 ? -1 : -2) (1 ? -1 : -2) (-1 ? 1 : 2)>;
+	or  = <(0 || 0) (0 || 1) (1 || 0) (1 || 1) (-0 || -0) (0 || -1) (1 || -0) (-1 || -1)>;
+	and = <(0 && 0) (0 && 1) (1 && 0) (1 && 1) (-0 && -0) (0 && -1) (1 && -0) (-1 && -1)>;
+
+	bo  = <(2 | 1) (2 | -1) (-1 | 0) (-2 | -1)>;
+	bx  = <(2 ^ 1) (2 ^ -1) (-1 ^ 0) (-2 ^ -1)>;
+	ba  = <(2 & 1) (2 & -1) (-1 & 0) (-2 & -1)>;
+
+	eq  = <(4 == 3) (-4 == -3) (4 == 4) (-4 == -4)>;
+	neq = <(4 != 3) (-4 != -3) (4 != 4) (-4 != -4)>;
+
+	l   = <(4 <  3) (-4 <  3) (4 < -3) (-4 <  -3) (-0 < 0)>;
+	g   = <(4 >  3) (-4 >  3) (4 > -3) (-4 >  -3) (-0 > 0)>;
+	leq = <(4 <= 3) (-4 <= 3) (4 <= -3) (-4 <= -3) (-0 <= 0)>;
+	geq = <(4 >= 3) (-4 >= 3) (4 >= -3) (-4 >= -3) (-0 >= 0)>;
+
+	lsh = <(1 << 1) (-1 << 1) (-1 << -1) (-1 << 64)>;
+	rsh = <(2 >> 1) (-4 >> 1) (-1 >> -1) (-1 >> 64) (-0 >> 31)>;
+
+	add = <(4 + 3) (-4 + 3) (4 + -3) (-4 + -3)>;
+	sub = <(4 - 3) (-4 - 3) (4 - -3) (-4 - -3)>;
+	mul = <(4 * 3) (-4 * 3) (4 * -3) (-4 * -3)>;
+	div = <(4 / 3) (-4 / 3) (4 / -3) (-4 / -3) (-0 / 1)>;
+	mod = <(4 % 3) (-4 % 3) (4 % -3) (-4 % -3) (-0 % 1)>;
+
+	neg     = <(-0) (--0) (-1) (--1)>;
+	bit-not = <(~0) (~-0) (~1) (~-1)>;
+	log-not = <(!0) (!-0) (!1) (!-1)>;
+
+	big-add = <(0xfffffffe + 1) (1 + 0xfffffffe) (0xffffffff + -1) (-1 + 0xffffffff) (1 + -0x80000000)>;
+	big-sub = <(0xffffffff - 1) (1 - 0xffffffff) (-0x80000000 - -0x80000000)>;
+	big-div = /bits/ 64 <(0x8000000000000000 / -1) (-0xffffffffffffffff / 2)  (-0 / 0xffffffffffffffff)>;
+	big-mod = /bits/ 64 <(0x8000000000000000 % -1) (-0 % 0xffffffffffffffff)>;
+	big-neg = <(-0xffffffff) (--0xffffffff) (-0x80000000) (--0x80000000)>;
+};
diff --git a/tests/run_tests.sh b/tests/run_tests.sh
index 294585b..2de44c0 100755
--- a/tests/run_tests.sh
+++ b/tests/run_tests.sh
@@ -618,8 +618,8 @@ dtc_tests () {
 	run_test dtbs_equal_ordered $tree odts_$tree.test.dtb
     done
 
-    # Check -Odts preserving type information
-    for tree in type-preservation.dts; do
+    # Check -Odts preserving type and sign information
+    for tree in type-preservation.dts sign-preservation.dts; do
         run_dtc_test -I dts -O dts -o $tree.test.dts "$SRCDIR/$tree"
         run_dtc_test -I dts -O dts $tree.test.dts
         run_wrap_test cmp "$SRCDIR/$tree" $tree.test.dts
@@ -631,9 +631,16 @@ dtc_tests () {
         run_test dtbs_equal_ordered $tree.test.dtb $tree.test.dts.test.dtb
     done
 
+    # Check -Odts supporting all operations
+    for tree in operations; do
+        run_dtc_test -I dts -O dts -o $tree.test.dts "$SRCDIR/$tree.dts"
+        run_dtc_test -I dts -O dts $tree.test.dts
+        run_wrap_test cmp "$SRCDIR/$tree-expected.dts" $tree.test.dts
+    done
+
     # Check -Oyaml output
     if ! $no_yaml; then
-            for tree in type-preservation; do
+            for tree in type-preservation sign-preservation operations; do
                 run_dtc_test -I dts -O yaml -o $tree.test.dt.yaml "$SRCDIR/$tree.dts"
                 run_wrap_test cmp "$SRCDIR/$tree.dt.yaml" $tree.test.dt.yaml
             done
diff --git a/tests/sign-preservation.dt.yaml b/tests/sign-preservation.dt.yaml
new file mode 100644
index 0000000..bc85f5f
--- /dev/null
+++ b/tests/sign-preservation.dt.yaml
@@ -0,0 +1,23 @@
+---
+- '#address-cells': [[0x1]]
+  '#size-cells': [[0x0]]
+  subnode@1:
+    reg: [[0x1]]
+    int-neg: [[-0x1]]
+    int-matrix: [[0x0, -0x1], [0xffffffff, -0x7fffffff]]
+    int-matrix-neg: [[-0x1, -0x2], [-0x7ffffffe, -0x7fffffff]]
+    int8-neg: [!u8 [-0x7f]]
+    int8-array: [!u8 [-0x1, 0x2, -0x7e, 0xff]]
+    int8-array-neg: [!u8 [-0x1, -0x2, -0x7e, -0x7f]]
+    int16-neg: [!u16 [-0x3210]]
+    int16-array: [!u16 [-0x1234, 0x5678, 0x90ab, -0x7def]]
+    int16-array-neg: [!u16 [-0x1234, -0x5678, -0x70ab, -0x7def]]
+    int16-matrix: [!u16 [0x1234, -0x5678], [-0x70ab, 0xcdef]]
+    int16-matrix-neg: [!u16 [-0x1234, -0x5678], [-0x70ab, -0x7def]]
+    int64-neg: [!u64 [-0x7fffffffffffffff]]
+    int64-array: [!u64 [0x1, 0xffffffffffffffff, -0x1, -0x7fffffffffffffff]]
+    int64-array-neg: [!u64 [-0x2, -0x8000000000000000]]
+    subsubnode:
+      subsubsubnode:
+        compatible: ["subsubsubnode1", [0x1234], [-0x1234], "subsubsubnode"]
+...
diff --git a/tests/sign-preservation.dts b/tests/sign-preservation.dts
new file mode 100644
index 0000000..b7f557c
--- /dev/null
+++ b/tests/sign-preservation.dts
@@ -0,0 +1,31 @@
+/dts-v1/;
+
+/ {
+	#address-cells = <0x01>;
+	#size-cells = <0x00>;
+
+	sub1: subnode@1 {
+		reg = <0x01>;
+		int-neg = <(-0x01)>;
+		int-matrix = <0x00 (-0x01)>, int_matrix_label: <0xffffffff (-0x7fffffff)>;
+		int-matrix-neg = <(-0x01) (-0x02)>, int_matrix_neg_label: <(-0x7ffffffe) (-0x7fffffff)>;
+		int8-neg = /bits/ 8 <(-0x7f)>;
+		int8-array = /bits/ 8 <(-0x01) 0x02 (-0x7e) 0xff>;
+		int8-array-neg = /bits/ 8 <(-0x01) (-0x02) (-0x7e) (-0x7f)>;
+		int16-neg = /bits/ 16 <(-0x3210)>;
+		int16-array = /bits/ 16 <(-0x1234) 0x5678 0x90ab (-0x7def)>;
+		int16-array-neg = /bits/ 16 <(-0x1234) (-0x5678) (-0x70ab) (-0x7def)>;
+		int16-matrix = /bits/ 16 <0x1234 (-0x5678)>, <(-0x70ab) 0xcdef>;
+		int16-matrix-neg = /bits/ 16 <(-0x1234) (-0x5678)>, <(-0x70ab) (-0x7def)>;
+		int64-neg = /bits/ 64 <(-0x7fffffffffffffff)>;
+		int64-array = /bits/ 64 <0x01 0xffffffffffffffff (-0x01) (-0x7fffffffffffffff)> int64_array_label_end:;
+		int64-array-neg = /bits/ 64 <(-0x02) (-0x8000000000000000)> int64_array_neg_label_end:;
+
+		subsub1: subsubnode {
+
+			subsubsub1: subsubsubnode {
+				compatible = "subsubsubnode1", <0x1234>, <(-0x1234)>, valuea: valueb: "subsubsubnode";
+			};
+		};
+	};
+};
-- 
2.17.1

Re: [PATCH v2 1/6] dtc: Avoid UB when shifting

[David Gibson]

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

On Tue, Jul 14, 2020 at 04:45:37PM +0100, Andrei Ziureaev wrote:
> Prevent undefined behavior when shifting by a number that's bigger than
> or equal to the width of the first operand.
> 
> Signed-off-by: Andrei Ziureaev <andrei.ziureaev-5wv7dgnIgG8@public.gmane.org>

This one makes sense independent of the rest.  Applied.

> ---
>  dtc-parser.y | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/dtc-parser.y b/dtc-parser.y
> index 40dcf4f..a0316a3 100644
> --- a/dtc-parser.y
> +++ b/dtc-parser.y
> @@ -476,8 +476,8 @@ integer_rela:
>  	;
>  
>  integer_shift:
> -	  integer_shift DT_LSHIFT integer_add { $$ = $1 << $3; }
> -	| integer_shift DT_RSHIFT integer_add { $$ = $1 >> $3; }
> +	  integer_shift DT_LSHIFT integer_add { $$ = ($3 < 64) ? ($1 << $3) : 0; }
> +	| integer_shift DT_RSHIFT integer_add { $$ = ($3 < 64) ? ($1 >> $3) : 0; }
>  	| integer_add
>  	;
>  

-- 
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 --]

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

[David Gibson]

[-- 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 --]