Bit fields, like in C

I'm surprised that this has never been proposed before!

I was thinking of putting this into a revision of my latest fixed-size array proposal, but it deserves separate discussion, at least for the search potential for others.

Basically, this idea brings bit fields from C. Besides improving conversion of C structures, we could use it to jam properties closer together.

/// A type that can be converted to and from a compact set of bits.
///
/// You can use any type that conforms to the `BitFieldRepresentable` protocol
/// for a property marked with the `@compact` attribute or as an associated
/// value for an enumeration case marked with that attribute.  Several
/// internally simple types in the standard library conform to
/// `BitFieldRepresentable`, such as most numeric types and `Bool`.  When a
/// containing type contains several members allowed to be compact, the compiler
/// may make several of them share a representation at the processor level,
/// reading and writing subsets of the shared representation's bits as needed to
/// realize a member at the user level.
///
/// Expressing a value of a type conforming to `BitFieldRepresentable` means
/// representing that value with a few bits as possible, while making sure each
/// distinct value of the conforming type maps to a distinct value of the
/// associated `CompactValue` type.  Unless the number of values is a power of
/// two, there will be unmapped compacted values that should not be permitted
/// for reverse-mapping.
///
/// Conforming to the BitFieldRepresentable Protocol
/// ================================================
///
/// To use your own custom type as part of a bit field, add
/// `BitFieldRepresentable` conformance to your type.
///
/// The compiler automatically synthesizes your custom type's
/// `BitFieldRepresentable` requirements when you declare conformance in the
/// type's original declaration and the type meets these criteria:
///
/// - For a `struct`, all of its instance-level stored properties must conform
///   to `BitFieldRepresentable`.
/// - For an `enum`, none of its cases use associated values.
///
/// Note that a tuple type automatically conforms to `BitFieldRepresentable` if
/// all of its members do, and a grid array type conforms if its element type
/// does.
///
/// To customize your type's `BitFieldRepresentable` conformance, to adopt
/// `BitFieldRepresentable` in a type that doesn't meet the crieteria listed
/// above, or to extend an existing type to conform to `BitFieldRepresentable`,
/// implement the `init(compactValue:)` initializer and `compactValue` property
/// in your custom type.
///
/// For example, the following type can make do with automatic synthesis:
///
///     struct Color: BitFieldRepresentable {
///         let useRed: Bool
///         let useGreen: Bool
///         let manyBlue: (high: [2 ; Bool], low: [2 ; Bool])
///     }
///
/// The `Color` type can be used compactly anywhere the compiler can fit six
/// bits.  A more complex type:
///
///     enum MoreColor {
///         case simple(Color)
///         case complex(Float16)
///     }
///
/// needs explicit work:
///
///     extension MoreColor: BitFieldRepresentable {
///         var compactValue: [17 ; Bool] {
///             var result: CompactValue = fill(false)
///             switch self {
///             case simple(let c):
///                 result[0] = false
///                 _ = result[1...6].copy(from: c.compactValue)
///             case complex(let f):
///                 result[0] = true
///                 _ = result[1...].copy(from: f.compactValue)
///             }
///         }
///
///         init?(compactValue: [17 ; Bool]) {
///             if compactValue[0] {
///                 let compactColor = compactValue[1...6]
///                 guard let color = Color(compactValue: compactColor) else {
///                     return nil
///                 }
///
///                 self = .simple(color)
///             } else {
///                 let compactFloat = compactValue[1...]
///                 guard let float = Float16(compactValue: compactFloat) else {
///                     return nil
///                 }
///
///                 self = .complex(float)
///             }
///         }
///     }
///
/// But now can be used compactly in a bigger type:
///
///     class MyApp {
///         @compact(Int32)
///         let colorParts: (base: MoreColor, extra: UInt8)
///
///         //...
///     }
protocol BitFieldRepresentable {

    /// The type that can represent all values of the conforming type, using as
    /// few composed Boolean states as possible.
    ///
    /// Every distinct value of the conforming type has a corresponding unique
    /// value of the `CompactValue` type, but there may be values of the
    /// `CompactValue` type that don't have a corresponding value of the
    /// conforming type.
    associatedtype CompactValue: [_! ; Bool]

    /// Creates a new instance from the specified compacted value.
    ///
    /// If there is no value of the type that corresponds with the specified
    /// compact value, this initializer returns `nil`. For example:
    ///
    ///     enum PaperSize {
    ///         case A2, A4, A5, Letter, Legal
    ///     }
    ///
    ///     print(PaperSize(compactValue: [false, false, false]))
    ///     // Prints "Optional(PaperSize.A2)"
    ///
    ///     print(PaperSize(compactValue: [true, true, true]))
    ///     // Prints "nil"
    ///
    /// - Parameter compactValue: The compact value to use for the new instance.
    init?(compactValue: CompactValue)

    /// The corresponding value of the compacted type.
    ///
    /// A new instance initialized with `compactValue` will be equivalent to
    /// this instance. For example:
    ///
    ///     enum PaperSize: String {
    ///         case A2, A4, A5, Letter, Legal
    ///     }
    ///
    ///     let selectedSize = PaperSize.Letter
    ///     print(selectedSize.compactValue.reversed())
    ///     // Prints "[false, true, true]"
    ///
    ///     print(selectedSize == PaperSize(rawValue: selectedSize.compactValue)!)
    ///     // Prints "true"
    var compactValue: CompactValue { get }

}

Where "[_! ; Bool]" is the pseudo-protocol for one-dimensional fixed-size arrays of Bool where the length has to be specified at compile time. (Any interface to FSAs besides single-element subscript is something I made on the fly and shouldn't be inferred to make it into another FSA proposal.) The "@compact" attribute is something else made on the fly. The attribute goes before a stored property or a enumeration case. The type of the targeted member has to be BitFieldRepresentable. When converted, the result has to fit within the type given in the attribute. The attribute can omit the containing type, in which the compiler will pick the best type.

If the conforming type is too large for any of default integer types, should a compile-time error be raised, or should the compact attribute be ignored?

The big problem is making small integers. C can make its multi-bit bit fields act as integer types because all its integer types are built-ins, and so the C runtime can do the translations between calculations. Swift deliberately puts the default integer types into the standard library instead of being built-ins. Either we make Int0, UInt0, Int1,... all the way to UInt63, which seems impractical, or use auxiliary functions to give one-dimensional Bool fixed-size arrays the integer operations. (Slapping FixedWidthInteger on every Bool FSA also seems like a bad idea.)

enum IntegerOperationsForBooleanGridArrays {

    public static func add<T: [_! ; Bool, U: [_! ; Bool]>(unsigned t: T, unsigned u: U) -> some [_! ; Bool]
    public static func add<T: [_! ; Bool, U: [_! ; Bool]>(unsigned t: T, signed u: U) -> some [_! ; Bool]
    public static func add<T: [_! ; Bool, U: [_! ; Bool]>(signed t: T, unsigned u: U) -> some [_! ; Bool]
    public static func add<T: [_! ; Bool, U: [_! ; Bool]>(signed t: T, signed u: U) -> some [_! ; Bool]

    // Do the same for: subtract, multiply, divide, modulus, quotient & remainder, negate, comparisons, etc.

}

Or just force the user to pick default integer types to use and convert themselves for doing math operations.

Bitfields are a notorious minefield in C and C++. They look like a thing you want to use at first, but their layout basically isn't specified by the language at all. They are occasionally useful if you only need to support a single compiler for a single hardware platform, but broadly speaking they cause more harm than good--it's almost always better to simply define a bunch of access functions that do your "bitfield" access explicitly with shifts and masks when you want to operate on a packed format.

I would only want to do this for Swift if we completely and unambiguously define the "compressed storage format" of fields. But we don't have a way to specify the layout of a "normal" struct in Swift yet (you have to define a C struct and import it instead), so this is somewhat putting the cart before the horse.

I don't think that there's any need to have a sea of types. The right way to model this (in my opinion) is to be able to define a "compressed storage format" for a type, and have the compiler emit the pack/unpack operations between that format and the "normal Swift struct" layout where necessary.

7 Likes

Swift has the OptionSet protocol to implement bitfields. It’s not very C-like but that’s good, as it works much like any other Swift struct or enum. I could write more but you should look at the documentation instead.

3 Likes

OptionSet is good at what it does, but it's only a piece of what is meant by "bitfields" in C or C++ (and it has some of the same difficulty as C bitfields around endianness and layout, which I would expect a complete "bitfield" proposal to solve).

2 Likes

I don't think we ever want a "specified layout" for most types, because it doesn't matter in the vast majority of cases, and we'd want to eventually be able to do automatic layout optimization to minimize padding, to pack Bools, enums, and other small fields into spare bits or bitfields automatically, to prune dead fields, and so on. It would be nice if the "actually I do want a fully specified layout" feature did support precise description of bit-packing, though.

Oh definitely. I don't want this for normal types, rather to be an opt-in thing (much like C bitfields are!)

If we ever have a "precise layout" feature, I think it should be directed squarely at use cases like network protocols and serialization. Language interoperation use cases should be handled by importing C headers. Storage optimization use cases should mostly be handled by (1) the compiler doing a certain amount of bit-packing of value types automatically, which will allow (2) programmers to rework their representations in order to take advantage of that.

That said, the compiler can't automatically compress to less than the formally-expressible range of a type. We can bit-pack Bool and frozen enums, but we'd still need some ability to just put a range constraint on an integer.

2 Likes

What makes you say that? I like the idea of repr(C) in Rust, isn't that something that's desirable to ultimately have?

1 Like

I personally don't see eliminating C headers as an interesting goal in and of itself. If you already have an existing C header that perfectly describes the interface you want to work with, you should just use that header instead of trying to duplicate it perfectly in Swift as an exercise.

2 Likes

repr(C) would require the entirety of C (including all of the various vendor-specific packing and layout extensions) to be reflected into Swift. By having C interop be through C headers, we can import types with the full expressivity of the C dialects Clang supports (including things like bitfields which are standard in C but have no current Swift equivalent) without having to translate everything precisely into Swift.

9 Likes
Terms of Service

Privacy Policy

Cookie Policy