prog: add bitfields to templates

Now it's possible to use `int32:18` to denote a bitfield of size 18 as a struct field.

This fixes #72.

4 files changed, 195 insertions, 112 deletions

diff --git a/sys/README.md b/sys/README.md
index e8f49b5b6..5a139f4f8 100644
--- a/sys/README.md
+++ b/sys/README.md
@@ -71,6 +71,27 @@ or for string flags as:
 	flagname = "\"" literal "\"" ["," "\"" literal "\""]*
 ```
 
+### Ints
+
+You can use `int8`, `int16`, `int32`, `int64` and `int64` to denote an integer of the corresponding size.
+
+By appending `be` suffix (like `int16be`) integers become big-endian.
+
+It's possible to specify range of values for an integer in the format of `int32[0:100]`.
+
+To denote a bitfield of size N use `int64:N`.
+
+It's possible to use these various kinds of ints as base types for `const`, `flags`, `len` and `proc`.
+
+```
+example_struct {
+	f0	int8			# random 1-byte integer
+	f1	const[0x42, int16be]	# const 2-byte integer with value 0x4200 (big-endian 0x42)
+	f2	int32[0:100]		# random 4-byte integer with values from 0 to 100 inclusive
+	f3	int64:20		# random 20-bit bitfield
+}
+```
+
 ### Structs
 
 Structs are described as:
diff --git a/sys/align.go b/sys/align.go
index 1b1ea66ac..8b9e1a3c2 100644
--- a/sys/align.go
+++ b/sys/align.go
@@ -3,6 +3,10 @@
 
 package sys
 
+import (
+	"fmt"
+)
+
 func initAlign() {
 	var rec func(t Type)
 	rec = func(t Type) {
@@ -17,6 +21,7 @@ func initAlign() {
 				for _, f := range t1.Fields {
 					rec(f)
 				}
+				markBitfields(t1)
 				addAlignment(t1)
 			}
 		case *UnionType:
@@ -31,6 +36,46 @@ func initAlign() {
 	}
 }
 
+func setBitfieldOffset(t Type, offset uintptr, last bool) {
+	switch t1 := t.(type) {
+	case *IntType:
+		t1.BitfieldOff = offset
+		t1.BitfieldLst = last
+	case *ConstType:
+		t1.BitfieldOff = offset
+		t1.BitfieldLst = last
+	case *LenType:
+		t1.BitfieldOff = offset
+		t1.BitfieldLst = last
+	case *FlagsType:
+		t1.BitfieldOff = offset
+		t1.BitfieldLst = last
+	case *ProcType:
+		t1.BitfieldOff = offset
+		t1.BitfieldLst = last
+	default:
+		panic(fmt.Sprintf("type %+v can't be a bitfield", t1))
+	}
+}
+
+func markBitfields(t *StructType) {
+	var bfOffset uintptr
+	for i, f := range t.Fields {
+		if f.BitfieldLength() == 0 {
+			continue
+		}
+		off, last := bfOffset, false
+		bfOffset += f.BitfieldLength()
+		if i == len(t.Fields)-1 || // Last bitfield in a group, if last field of the struct...
+			t.Fields[i+1].BitfieldLength() == 0 || // or next field is not a bitfield...
+			f.Size() != t.Fields[i+1].Size() || // or next field is of different size...
+			bfOffset+t.Fields[i+1].BitfieldLength() > f.Size()*8 { // or next field does not fit into the current group.
+			last, bfOffset = true, 0
+		}
+		setBitfieldOffset(f, off, last)
+	}
+}
+
 func addAlignment(t *StructType) {
 	if t.packed {
 		return
@@ -43,10 +88,13 @@ func addAlignment(t *StructType) {
 		if align < a {
 			align = a
 		}
-		if off%a != 0 {
-			pad := a - off%a
-			off += pad
-			fields = append(fields, makePad(pad))
+		if i > 0 && (t.Fields[i-1].BitfieldLength() == 0 || t.Fields[i-1].BitfieldLast()) {
+			// Append padding if the last field is not a bitfield or it's the last bitfield in a set.
+			if off%a != 0 {
+				pad := a - off%a
+				off += pad
+				fields = append(fields, makePad(pad))
+			}
 		}
 		fields = append(fields, f)
 		if at, ok := f.(*ArrayType); ok && (at.Kind == ArrayRandLen || (at.Kind == ArrayRangeLen && at.RangeBegin != at.RangeEnd)) {
@@ -58,7 +106,8 @@ func addAlignment(t *StructType) {
 		if varLen && i != len(t.Fields)-1 {
 			panic("embed array in middle of a struct")
 		}
-		if !varLen {
+		if (f.BitfieldLength() == 0 || f.BitfieldLast()) && !varLen {
+			// Increase offset if the current field is not a bitfield or it's the last bitfield in a set.
 			off += f.Size()
 		}
 	}
@@ -72,9 +121,11 @@ func addAlignment(t *StructType) {
 
 func makePad(sz uintptr) Type {
 	return &ConstType{
-		TypeCommon: TypeCommon{TypeName: "pad", IsOptional: false},
-		TypeSize:   sz,
-		Val:        0,
-		IsPad:      true,
+		IntTypeCommon: IntTypeCommon{
+			TypeCommon: TypeCommon{TypeName: "pad", IsOptional: false},
+			TypeSize:   sz,
+		},
+		Val:   0,
+		IsPad: true,
 	}
 }
diff --git a/sys/decl.go b/sys/decl.go
index aa59e8e0a..9c7887f99 100644
--- a/sys/decl.go
+++ b/sys/decl.go
@@ -34,6 +34,9 @@ type Type interface {
 	Default() uintptr
 	Size() uintptr
 	Align() uintptr
+	BitfieldOffset() uintptr
+	BitfieldLength() uintptr
+	BitfieldLast() bool
 }
 
 func IsPad(t Type) bool {
@@ -61,6 +64,18 @@ func (t *TypeCommon) Default() uintptr {
 	return 0
 }
 
+func (t *TypeCommon) BitfieldOffset() uintptr {
+	return 0
+}
+
+func (t *TypeCommon) BitfieldLength() uintptr {
+	return 0
+}
+
+func (t *TypeCommon) BitfieldLast() bool {
+	return false
+}
+
 func (t TypeCommon) Dir() Dir {
 	return t.ArgDir
 }
@@ -97,6 +112,88 @@ func (t *ResourceType) Align() uintptr {
 	return t.Desc.Type.Align()
 }
 
+type IntTypeCommon struct {
+	TypeCommon
+	TypeSize    uintptr
+	BigEndian   bool
+	BitfieldOff uintptr
+	BitfieldLen uintptr
+	BitfieldLst bool
+}
+
+func (t *IntTypeCommon) Size() uintptr {
+	return t.TypeSize
+}
+
+func (t *IntTypeCommon) Align() uintptr {
+	return t.Size()
+}
+
+func (t *IntTypeCommon) BitfieldOffset() uintptr {
+	return t.BitfieldOff
+}
+
+func (t *IntTypeCommon) BitfieldLength() uintptr {
+	return t.BitfieldLen
+}
+
+func (t *IntTypeCommon) BitfieldLast() bool {
+	return t.BitfieldLst
+}
+
+type ConstType struct {
+	IntTypeCommon
+	Val   uintptr
+	IsPad bool
+}
+
+type IntKind int
+
+const (
+	IntPlain IntKind = iota
+	IntSignalno
+	IntFileoff // offset within a file
+	IntRange
+)
+
+type IntType struct {
+	IntTypeCommon
+	Kind       IntKind
+	RangeBegin int64
+	RangeEnd   int64
+}
+
+type FlagsType struct {
+	IntTypeCommon
+	Vals []uintptr
+}
+
+type LenType struct {
+	IntTypeCommon
+	ByteSize uintptr // want size in multiple of bytes instead of array size
+	Buf      string
+}
+
+type ProcType struct {
+	IntTypeCommon
+	ValuesStart   int64
+	ValuesPerProc uint64
+}
+
+type VmaType struct {
+	TypeCommon
+	RangeBegin int64 // in pages
+	RangeEnd   int64
+}
+
+func (t *VmaType) Size() uintptr {
+	return ptrSize
+}
+
+func (t *VmaType) Align() uintptr {
+	return t.Size()
+}
+
 type BufferKind int
 
 const (
@@ -153,109 +250,6 @@ func (t *BufferType) Align() uintptr {
 	return 1
 }
 
-type VmaType struct {
-	TypeCommon
-	RangeBegin int64 // in pages
-	RangeEnd   int64
-}
-
-func (t *VmaType) Size() uintptr {
-	return ptrSize
-}
-
-func (t *VmaType) Align() uintptr {
-	return t.Size()
-}
-
-type LenType struct {
-	TypeCommon
-	TypeSize  uintptr
-	BigEndian bool
-	ByteSize  uintptr // want size in multiple of bytes instead of array size
-	Buf       string
-}
-
-func (t *LenType) Size() uintptr {
-	return t.TypeSize
-}
-
-func (t *LenType) Align() uintptr {
-	return t.Size()
-}
-
-type FlagsType struct {
-	TypeCommon
-	TypeSize  uintptr
-	BigEndian bool
-	Vals      []uintptr
-}
-
-func (t *FlagsType) Size() uintptr {
-	return t.TypeSize
-}
-
-func (t *FlagsType) Align() uintptr {
-	return t.Size()
-}
-
-type ConstType struct {
-	TypeCommon
-	TypeSize  uintptr
-	BigEndian bool
-	Val       uintptr
-	IsPad     bool
-}
-
-func (t *ConstType) Size() uintptr {
-	return t.TypeSize
-}
-
-func (t *ConstType) Align() uintptr {
-	return t.Size()
-}
-
-type IntKind int
-
-const (
-	IntPlain IntKind = iota
-	IntSignalno
-	IntFileoff // offset within a file
-	IntRange
-)
-
-type IntType struct {
-	TypeCommon
-	TypeSize   uintptr
-	BigEndian  bool
-	Kind       IntKind
-	RangeBegin int64
-	RangeEnd   int64
-}
-
-func (t *IntType) Size() uintptr {
-	return t.TypeSize
-}
-
-func (t *IntType) Align() uintptr {
-	return t.Size()
-}
-
-type ProcType struct {
-	TypeCommon
-	TypeSize      uintptr
-	BigEndian     bool
-	ValuesStart   int64
-	ValuesPerProc uint64
-}
-
-func (t *ProcType) Size() uintptr {
-	return t.TypeSize
-}
-
-func (t *ProcType) Align() uintptr {
-	return t.Size()
-}
-
 type ArrayKind int
 
 const (
diff --git a/sys/test.txt b/sys/test.txt
index 2c7eb0d0c..aa9ea1ab0 100644
--- a/sys/test.txt
+++ b/sys/test.txt
@@ -217,3 +217,20 @@ syz_test$regression0(a0 ptr[inout, syz_regression0_struct])
 syz_regression0_struct {
 	f0	buffer[out]
 }
+
+# Bitfields.
+
+syz_bf_flags = 0, 1, 2
+
+syz_bf_struct {
+	f0	flags[syz_bf_flags, int16:10]
+	f1	int64
+	f2	const[0x42, int16:5]
+	f3	int16:6
+	f4	const[0x42, int32:15]
+	f5	len[parent, int16:11]
+	f6	len[parent, int16be:11]
+	f7	int8
+}
+
+syz_test$bf(a0 ptr[in, syz_bf_struct])