Re: std.bitmanip help - how to combine bitfields and read
On Wednesday, 11 March 2020 at 05:25:43 UTC, kookman wrote:
I am using libpcap to read from stored pcap files, and want to
use std.bitmanip.bitfields to read TCP flags from the file,
using a struct like:
struct TcpHeader {
align(1):
ushort srcPort;
ushort dstPort;
uint seqNo;
uint ackNo;
mixin(bitfields!(
bool, "flagFin", 1,
bool, "flagSyn", 1,
bool, "flagRst", 1,
bool, "flagPsh", 1,
bool, "flagAck", 1,
bool, "flagUrg", 1,
bool, "flagEce", 1,
bool, "flagCwr", 1,
bool, "flagNs", 1,
ubyte, "reserved", 3,
ubyte, "dataOffsetWords", 4 // in 32bit words, min=5,
max=15
));
ushort windowSize;
ushort checksum;
ushort urgentPtr;
this(inout ubyte[] bytes)
{
srcPort = bytes.read!ushort();
dstPort = bytes.read!ushort();
seqNo = bytes.read!uint();
ackNo = bytes.read!uint();
// now what? how to read bitfields??
}
const uint dataOffset()// convenience method to get
offset in bytes
{
return dataOffsetWords * 4;
}
}
How can I get at the private field behind the bitfields to read
into it. I'm using std.bitmanip.read because I need the network
order (bigendian) conversion for this data.
Actually, doing it a "smarter" way worked:
struct TcpHeader {
align(1):
ushort srcPort;
ushort dstPort;
uint seqNo;
uint ackNo;
mixin(bitfields!(
bool, "flagFin", 1,
bool, "flagSyn", 1,
bool, "flagRst", 1,
bool, "flagPsh", 1,
bool, "flagAck", 1,
bool, "flagUrg", 1,
bool, "flagEce", 1,
bool, "flagCwr", 1,
bool, "flagNs", 1,
ubyte, "reserved", 3,
ubyte, "dataOffsetWords", 4 // in 32bit words, min=5,
max=15
));
ushort windowSize;
ushort checksum;
ushort urgentPtr;
this(inout(ubyte)[] bytes)
{
import std.traits: FieldNameTuple;
static foreach (f; FieldNameTuple!TcpHeader) {
pragma(msg, f);
__traits(getMember, this, f) =
bytes.read!(typeof(__traits(getMember, this, f)));
}
}
const uint dataOffset()// convenience method to get
offset in bytes
{
return dataOffsetWords * 4;
}
}
std.bitmanip help - how to combine bitfields and read
I am using libpcap to read from stored pcap files, and want to
use std.bitmanip.bitfields to read TCP flags from the file, using
a struct like:
struct TcpHeader {
align(1):
ushort srcPort;
ushort dstPort;
uint seqNo;
uint ackNo;
mixin(bitfields!(
bool, "flagFin", 1,
bool, "flagSyn", 1,
bool, "flagRst", 1,
bool, "flagPsh", 1,
bool, "flagAck", 1,
bool, "flagUrg", 1,
bool, "flagEce", 1,
bool, "flagCwr", 1,
bool, "flagNs", 1,
ubyte, "reserved", 3,
ubyte, "dataOffsetWords", 4 // in 32bit words, min=5,
max=15
));
ushort windowSize;
ushort checksum;
ushort urgentPtr;
this(inout ubyte[] bytes)
{
srcPort = bytes.read!ushort();
dstPort = bytes.read!ushort();
seqNo = bytes.read!uint();
ackNo = bytes.read!uint();
// now what? how to read bitfields??
}
const uint dataOffset()// convenience method to get
offset in bytes
{
return dataOffsetWords * 4;
}
}
How can I get at the private field behind the bitfields to read
into it. I'm using std.bitmanip.read because I need the network
order (bigendian) conversion for this data.
Re: Bitfields
On Wednesday, 22 May 2019 at 08:54:45 UTC, Russel Winder wrote: On Tue, 2019-05-21 at 19:14 +, Era Scarecrow via Digitalmars-d-learn wrote: […] I worked on/with bitfields in the past, the limit sizes is more or less for natural int types that D supports. Rust bitfield crate and it's macros are the same, the underlying type for a bitfield must be a primitive integer type. Fortunately, Rust has i128 and u128 which is enough for my 112 bit EIT header. Boris Barboris suggested using BitArray and I willinvestigate but the size_t/byte problem would need to go away. However this limitation is kinda arbitrary, as for simplicity it relies on shifting bits, going larger or any byte size is possible depending on what needs to be stored, but ti's the speed that really takes a penalty when you aren't using native types or you have to do a lot of shifting to get the job done. What's the layout of what you need? I'll see if i can't make something that would work for you. Would be better if you can use a object that breaks the parts down and you can actually fully access those parts, then just re-store it into the limited space you want for storage, which then would be faster than bitfields (although not by much) I found an interesting way forward in the source code of dvbsnoop. It basically uses the byte sequence as a backing store and then has a function to do the necessary accesses to treat it as a bit array. If D's Bit Array can work with bytes instead of size_t then it is exactly what dvbsnoop does (in C) but adds writing as well as reading. The Rust solution using bitfield with a u128 backing it seems to work, but it is all very clumsy even if it is efficacious. If the type of operations you need on your 128 bit container is simple enough (bitwise op) you can implement them, backed by two ulong in a custom struct. I did something similar for the tokens if my language[1]. There are probably wrong stuff in there but for my usage (include and bt) that works seamlessly. [1]: https://github.com/Basile-z/styx/blob/master/src/styx/data_structures.d#L40
Re: Bitfields
On Tue, 2019-05-21 at 19:14 +, Era Scarecrow via Digitalmars-d-learn wrote: > […] > I worked on/with bitfields in the past, the limit sizes is more > or less for natural int types that D supports. Rust bitfield crate and it's macros are the same, the underlying type for a bitfield must be a primitive integer type. Fortunately, Rust has i128 and u128 which is enough for my 112 bit EIT header. Boris Barboris suggested using BitArray and I willinvestigate but the size_t/byte problem would need to go away. > However this limitation is kinda arbitrary, as for simplicity it > relies on shifting bits, going larger or any byte size is > possible depending on what needs to be stored, but ti's the speed > that really takes a penalty when you aren't using native types or > you have to do a lot of shifting to get the job done. > > What's the layout of what you need? I'll see if i can't make > something that would work for you. > > Would be better if you can use a object that breaks the parts > down and you can actually fully access those parts, then just > re-store it into the limited space you want for storage, which > then would be faster than bitfields (although not by much) I found an interesting way forward in the source code of dvbsnoop. It basically uses the byte sequence as a backing store and then has a function to do the necessary accesses to treat it as a bit array. If D's Bit Array can work with bytes instead of size_t then it is exactly what dvbsnoop does (in C) but adds writing as well as reading. The Rust solution using bitfield with a u128 backing it seems to work, but it is all very clumsy even if it is efficacious. -- Russel. === Dr Russel Winder t: +44 20 7585 2200 41 Buckmaster Roadm: +44 7770 465 077 London SW11 1EN, UK w: www.russel.org.uk signature.asc Description: This is a digitally signed message part
Re: Bitfields
On Tue, 2019-05-21 at 18:22 +, Boris-Barboris via Digitalmars-d-learn wrote: […] > > Never used it myself, but BitArray with careful handling of > endianess might fit your task. > > https://dlang.org/phobos/std_bitmanip.html#.BitArray.this.2 > https://dlang.org/phobos/std_bitmanip.html#.peek I'll have to mull that one over. The incoming data is a sequence of bytes that is treated as a bitfield. Although the standard says "big-endian" it is isn't entirely clear how this relates to the bitfields, I guess I need to read the standard more. :-( I guess the question is whether BitArray can work with bytes rather than size_t as elements of the backing array. -- Russel. === Dr Russel Winder t: +44 20 7585 2200 41 Buckmaster Roadm: +44 7770 465 077 London SW11 1EN, UK w: www.russel.org.uk signature.asc Description: This is a digitally signed message part
Re: Bitfields
On Tuesday, 21 May 2019 at 17:16:05 UTC, Russel Winder wrote: As far as I can see std.bitmanip only caters for 8, 16, 32, and 64 bit long bitfields. I worked on/with bitfields in the past, the limit sizes is more or less for natural int types that D supports. However this limitation is kinda arbitrary, as for simplicity it relies on shifting bits, going larger or any byte size is possible depending on what needs to be stored, but ti's the speed that really takes a penalty when you aren't using native types or you have to do a lot of shifting to get the job done. What's the layout of what you need? I'll see if i can't make something that would work for you. Would be better if you can use a object that breaks the parts down and you can actually fully access those parts, then just re-store it into the limited space you want for storage, which then would be faster than bitfields (although not by much)
Re: Bitfields
On Tuesday, 21 May 2019 at 17:16:05 UTC, Russel Winder wrote: Hi, Has anyone used D to work with arbitrary length bitfields with multiple occurences of a sub-bitfield. I am working with DVB Sections and EIT packets are defined as bitfields with loops in them and the header is 112 bits. The loops are handleable with subfields obviously, assuming you can work out how the bigendian works on the byte sequence. As far as I can see std.bitmanip only caters for 8, 16, 32, and 64 bit long bitfields. Never used it myself, but BitArray with careful handling of endianess might fit your task. https://dlang.org/phobos/std_bitmanip.html#.BitArray.this.2 https://dlang.org/phobos/std_bitmanip.html#.peek
Bitfields
Hi, Has anyone used D to work with arbitrary length bitfields with multiple occurences of a sub-bitfield. I am working with DVB Sections and EIT packets are defined as bitfields with loops in them and the header is 112 bits. The loops are handleable with subfields obviously, assuming you can work out how the bigendian works on the byte sequence. As far as I can see std.bitmanip only caters for 8, 16, 32, and 64 bit long bitfields. -- Russel. === Dr Russel Winder t: +44 20 7585 2200 41 Buckmaster Roadm: +44 7770 465 077 London SW11 1EN, UK w: www.russel.org.uk signature.asc Description: This is a digitally signed message part
Re: question about bitfields to decode websocket header
On Wednesday, 7 November 2018 at 14:22:43 UTC, lithium iodate wrote: On Wednesday, 7 November 2018 at 13:05:49 UTC, test wrote: I am confused about the bitfields order. The bitfields start with the least significant bits: fin -> 1 rsv1 -> 0 rsv2 -> 0 rsv3 -> 0 opcode -> 1000 = 8 mask -> 1 _size -> 101 = 65 This order will likely be what you want: mixin(bitfields!( opcode, "opcode", 4, bool, "rsv3", 1, bool, "rsv2", 1, bool, "rsv1", 1, bool, "fin",1, ubyte, "_size", 7, bool, "mask", 1, )); Also beware of endianness when mapping bytes to it. After I use your code it working now. my other question is: if the opcode bit cross byte, how do we define the bitfields ? for example if the opcode is a 6 bit number instead 4bit : F1|R1|R1|R1|opcode6|Mask1|Size5 I has to split the opcode here ? mixin(bitfields!( opcode, "opcode4", 4, bool, "rsv3", 1, bool, "rsv2", 1, bool, "rsv1", 1, bool, "fin",1, ubyte, "_size", 5, bool, "mask", 1, bool, "opcode2", 1, ));
Re: question about bitfields to decode websocket header
On Wednesday, 7 November 2018 at 13:05:49 UTC, test wrote: I am confused about the bitfields order. mixin(bitfields!( bool, "fin",1, bool, "rsv1", 1, bool, "rsv2", 1, bool, "rsv3", 1, Opcode, "opcode", 4, bool, "mask", 1, ubyte, "_size", 7, )); output for first byte is 1001 , the 2st byte 1011 my code output: opcode=8 mask=true size=65 the real size is 3 byte, and opcode is 1; how to fix this ? The bitfields start with the least significant bits: fin -> 1 rsv1 -> 0 rsv2 -> 0 rsv3 -> 0 opcode -> 1000 = 8 mask -> 1 _size -> 101 = 65 This order will likely be what you want: mixin(bitfields!( opcode, "opcode", 4, bool, "rsv3", 1, bool, "rsv2", 1, bool, "rsv1", 1, bool, "fin",1, ubyte, "_size", 7, bool, "mask", 1, )); Also beware of endianness when mapping bytes to it.
question about bitfields to decode websocket header
I am confused about the bitfields order. mixin(bitfields!( bool, "fin",1, bool, "rsv1", 1, bool, "rsv2", 1, bool, "rsv3", 1, Opcode, "opcode", 4, bool, "mask", 1, ubyte, "_size", 7, )); output for first byte is 1001 , the 2st byte 1011 my code output: opcode=8 mask=true size=65 the real size is 3 byte, and opcode is 1; how to fix this ?
bitfields comparison in opEquals
I have a struct with a mixin(bitfields) containing many small
bitfields. I also have a class member in the struct.
And because I want the class member to compare by using `is` I
need to define
bool opEquals(const scope typeof(this) that) const @safe pure
nothrow @nogc
{
return (this.data == that.data &&
this.context is that.context &&
// these are all bitfields members
// TODO can we do this comparison in one go?
this.lang == that.lang &&
this.pot == that.pot &&
this.manner == that.manner &&
this.senseNr == that.senseNr &&
this.hasUniquePot == that.hasUniquePot &&
this.isHashed == that.isHashed);
}
Is there a way to make the bitfields-comparsion in opEquals run
faster by somehow checking for its size in words (n) and casting
it to size_t[n] which can be compared very fast.
Re: OK, I'm stumped on this one: dstep, struct, mixin, bitfields
On Thursday, 22 March 2018 at 09:55:44 UTC, Russel Winder wrote: I am guessing you mean against DStep rather than D :-) Yes :) Though clearly T and I would prefer version not to be a D keyword. I suspect I have seen one place where DStep has turned version into version_ where version was a variable name. In this case "version" was a string used to create a bitfield using a mixin(bitfield!(…)) construct. Is that likely easy to fix? Yes. It's not a string literal in the C code. The identifier should be renamed before it's added to the call to "bitfield". -- /Jacob Carlborg
Re: OK, I'm stumped on this one: dstep, struct, mixin, bitfields
On Wednesday, 21 March 2018 at 19:41:39 UTC, H. S. Teoh wrote:
version(all) { ... }
version(none) { ... }
version(Posix) { ... }
version(Windows) { ... }
But yeah, using "version" for this purpose makes the very
common identifier "version" unavailable for use. I've been
bitten by this multiple times.
auto version = getVersion();// NG
auto ver = getVersion();// OK
struct PacketHeader {
ushort version; // NG
ushort ver; // OK
}
C code also uses `in`, `out` and `with` as identifiers.
I think, with some funny escape sequences we can do without any
keyword at all:
\1(all) { ... }
\1(none) { ... }
\1(Posix) { ... }
\1(Windows) { ... }
\5 version = getVersion();
\2 PacketHeader {
\6 version;
}
Re: OK, I'm stumped on this one: dstep, struct, mixin, bitfields
On Wed, 2018-03-21 at 22:18 +0100, Jacob Carlborg via Digitalmars-d-learn wrote: > On 2018-03-21 20:30, Russel Winder wrote: > > > Thanks to Adam and Ali, it was clear and obvious. > > Please report and issue so it's not forgotten. I am guessing you mean against DStep rather than D :-) Though clearly T and I would prefer version not to be a D keyword. I suspect I have seen one place where DStep has turned version into version_ where version was a variable name. In this case "version" was a string used to create a bitfield using a mixin(bitfield!(…)) construct. Is that likely easy to fix? -- Russel. == Dr Russel Winder t: +44 20 7585 2200 41 Buckmaster Roadm: +44 7770 465 077 London SW11 1EN, UK w: www.russel.org.uk signature.asc Description: This is a digitally signed message part
Re: OK, I'm stumped on this one: dstep, struct, mixin, bitfields
On 2018-03-21 20:30, Russel Winder wrote: Thanks to Adam and Ali, it was clear and obvious. Please report and issue so it's not forgotten. -- /Jacob Carlborg
Re: OK, I'm stumped on this one: dstep, struct, mixin, bitfields
On Wed, Mar 21, 2018 at 07:30:28PM +, Russel Winder via Digitalmars-d-learn
wrote:
[...]
> But :-(
>
> Why does version have to be a keyword?
[...]
version(all) { ... }
version(none) { ... }
version(Posix) { ... }
version(Windows) { ... }
But yeah, using "version" for this purpose makes the very common
identifier "version" unavailable for use. I've been bitten by this
multiple times.
auto version = getVersion();// NG
auto ver = getVersion();// OK
struct PacketHeader {
ushort version; // NG
ushort ver; // OK
}
:-(
T
--
Маленькие детки - маленькие бедки.
Re: OK, I'm stumped on this one: dstep, struct, mixin, bitfields
On Wed, 2018-03-21 at 18:11 +, Adam D. Ruppe via Digitalmars-d- learn wrote: > On Wednesday, 21 March 2018 at 18:00:38 UTC, Russel Winder wrote: > > ubyte, "version", 5, > > > version is a D keyword, so I would suggest trying "version_" > there instead and see if it works. (I'm guessing btw, the error > message was way to long and illegible, but this is an easy first > guess anyway) On Wed, 2018-03-21 at 11:14 -0700, Ali Çehreli via Digitalmars-d-learn wrote: […] > > I think it's because 'version' is a D keyword. :) > > Ali > Thanks to Adam and Ali, it was clear and obvious. But :-( Why does version have to be a keyword? -- Russel. === Dr Russel Winder t: +44 20 7585 2200 41 Buckmaster Roadm: +44 7770 465 077 London SW11 1EN, UK w: www.russel.org.uk signature.asc Description: This is a digitally signed message part
Re: OK, I'm stumped on this one: dstep, struct, mixin, bitfields
On 03/21/2018 11:00 AM, Russel Winder wrote: > The code I am playing with generated by DStep involves lots of lots of > structs with mixin bitfields. All of them seem to compile file, except > one. How is it that: > > mixin(bitfields!( > ubyte, "current_next", 1, > ubyte, "version", 5, > ubyte, "one2", 2)); /* TS ID */ > > can result in the following error. The line for "version" is 141 and > the one for "one2" is 142. I think it's because 'version' is a D keyword. :) Ali
Re: OK, I'm stumped on this one: dstep, struct, mixin, bitfields
On Wednesday, 21 March 2018 at 18:00:38 UTC, Russel Winder wrote: ubyte, "version", 5, version is a D keyword, so I would suggest trying "version_" there instead and see if it works. (I'm guessing btw, the error message was way to long and illegible, but this is an easy first guess anyway)
OK, I'm stumped on this one: dstep, struct, mixin, bitfields
The code I am playing with generated by DStep involves lots of lots of
structs with mixin bitfields. All of them seem to compile file, except
one. How is it that:
mixin(bitfields!(
ubyte, "current_next", 1,
ubyte, "version", 5,
ubyte, "one2", 2)); /* TS ID */
can result in the following error. The line for "version" is 141 and
the one for "one2" is 142.
source/libdvbv5_d/header.d-mixin-139(141): Error: no identifier for declarator
`ubyte`
source/libdvbv5_d/header.d-mixin-139(141): Error: identifier or integer
expected inside version(...), not `)`
source/libdvbv5_d/header.d-mixin-139(141): Error: found `@` when expecting `)`
source/libdvbv5_d/header.d-mixin-139(141): Error: no identifier for declarator
`safe`
source/libdvbv5_d/header.d-mixin-139(141): Error: declaration expected, not
`return`
source/libdvbv5_d/header.d-mixin-139(142): Error: no identifier for declarator
`void`
source/libdvbv5_d/header.d-mixin-139(142): Error: identifier or integer
expected inside version(...), not `ubyte`
source/libdvbv5_d/header.d-mixin-139(142): Error: found `v` when expecting `)`
source/libdvbv5_d/header.d-mixin-139(142): Error: declaration expected, not `)`
source/libdvbv5_d/header.d-mixin-139(142): Error: declaration expected, not
`assert`
source/libdvbv5_d/header.d-mixin-139(142): Error: no identifier for declarator
`_current_next_version_one2`
source/libdvbv5_d/header.d-mixin-139(142): Error: declaration expected, not `=`
source/libdvbv5_d/header.d(139): Error: incomplete mixin declaration `"private
ubyte _current_next_version_one2;@property ubyte current_next() @safe pure
nothrow @nogc const { auto result = (_current_next_version_one2 & 1U) >>0U;
return cast(ubyte) result;}\x0a@property void current_next(ubyte v) @safe pure
nothrow @nogc { assert(v >= current_next_min, \"Value is smaller than the
minimum value of bitfield 'current_next'\"); assert(v <= current_next_max,
\"Value is greater than the maximum value of bitfield 'current_next'\");
_current_next_version_one2 = cast(typeof(_current_next_version_one2))
((_current_next_version_one2 & (-1-cast(typeof(_current_next_version_one2))1U))
| ((cast(typeof(_current_next_version_one2)) v << 0U) & 1U));}\x0aenum ubyte
current_next_min = cast(ubyte)0U; enum ubyte current_next_max = cast(ubyte)1U;
@property ubyte version() @safe pure nothrow @nogc const { auto result =
(_current_next_version_one2 & 62U) >>1U; return cast(ubyte)
result;}\x0a@property void version(ubyte v) @safe pure nothrow @nogc { assert(v
>= version_min, \"Value is smaller than the minimum value of bitfield
'version'\"); assert(v <= version_max, \"Value is greater than the maximum
value of bitfield 'version'\"); _current_next_version_one2 =
cast(typeof(_current_next_version_one2)) ((_current_next_version_one2 &
(-1-cast(typeof(_current_next_version_one2))62U)) |
((cast(typeof(_current_next_version_one2)) v << 1U) & 62U));}\x0aenum ubyte
version_min = cast(ubyte)0U; enum ubyte version_max = cast(ubyte)31U;
@property ubyte one2() @safe pure nothrow @nogc const { auto result =
(_current_next_version_one2 & 192U) >>6U; return cast(ubyte)
result;}\x0a@property void one2(ubyte v) @safe pure nothrow @nogc { assert(v >=
one2_min, \"Value is smaller than the minimum value of bitfield 'one2'\");
assert(v <= one2_max, \"Value is greater than the maximum value of bitfield
'one2'\"); _current_next_version_one2 =
cast(typeof(_current_next_version_one2)) ((_current_next_version_one2 &
(-1-cast(typeof(_current_next_version_one2))192U)) |
((cast(typeof(_current_next_version_one2)) v << 6U) & 192U));}\x0aenum ubyte
one2_min = cast(ubyte)0U; enum ubyte one2_max = cast(ubyte)3U; "`
--
Russel.
===
Dr Russel Winder t: +44 20 7585 2200
41 Buckmaster Roadm: +44 7770 465 077
London SW11 1EN, UK w: www.russel.org.uk
signature.asc
Description: This is a digitally signed message part
Re: iterating through members of bitfields
Thank you both!
Re: iterating through members of bitfields
On 01/19/2017 05:21 PM, Nestor wrote:
On Wednesday, 18 January 2017 at 12:52:56 UTC, drug wrote:
I've "solved" the same problem by using AliasSeq to generate bitfields
so that for iterating over bitfields I can iterate over alias sequence
and mixin code. Not very good but it works.
Interesting, could you provide a working example?
Here is 'iterableBitfields' that mixes in both a static array of bit
field specs and a range that iterates through their values. Obviously,
because the range must have one element type, you have to specify what
works you: int, string, etc.
import std.stdio;
import std.bitmanip;
import std.string;
import std.typecons;
import std.conv;
import std.algorithm;
string makeBitfieldSpecs(IterValueType, Args...)(string specsPrefix) {
static assert(Args.length % 3 == 0);
string members;
string type;
string name;
size_t width;
string value;
foreach (i, arg; Args) {
static if (i % 3 == 0) {
type = arg.stringof;
}
else static if (i % 3 == 1) {
name = arg;
}
else {
width = arg;
value = format("(typeof(this) obj) => obj.%s().to!%s",
name, IterValueType.stringof);
members ~= format(`tuple("%s", "%s", %s, %s),`,type, name,
width, value);
}
}
string specsArray = format("static const %sSpecs = [ %s ];",
specsPrefix, members);
string specsFunc = format(q{
auto %sValues() const {
return %sSpecs.map!(spec => spec[3](this));
}}, specsPrefix, specsPrefix);
return specsArray ~ specsFunc;
}
string iterableBitfields(string specsPrefix, IterValueType, Args...)() {
return bitfields!Args ~ makeBitfieldSpecs!(IterValueType,
Args)(specsPrefix);
}
struct S {
int myVar;
mixin (iterableBitfields!("myFields", // prefix for names of
mixed-in array and func
int,// the type to present field
values in (can be string)
// Regular args to std.typecons.bitfields
follow:
int, "a", 24,
byte, "b", 8));
}
void main() {
auto s = S();
s.myVar = 42;
s.a = 1;
s.b = 2;
/* The struct gains two additional members:
*Specs: An array of tuples
*Values: A range of field values
*/
writefln("The specs (last one is a lambda):\n%( %s\n%)",
s.myFieldsSpecs);
writefln("The values: %(%s, %)", s.myFieldsValues);
// You must pass the object when calling the value lambda explicitly.
// Here is the value of 'a' through the lambda in the spec:
assert(s.a == s.myFieldsSpecs[0][3](s)); // Note 's' is passed to
lambda
}
Ali
Re: iterating through members of bitfields
20.01.2017 15:04, Nestor пишет: Where does one define the size for a field using AliasSeq, and in this example, why does it take 1 bit if the size is not declared anywhere? Something like that https://goo.gl/zV8T23
Re: iterating through members of bitfields
20.01.2017 15:04, Nestor пишет:
On Friday, 20 January 2017 at 08:13:08 UTC, drug wrote:
Something like that https://goo.gl/C4nOqw
Because you generate code iterating over AliasSeq you can do almost
everything you need - for example generate setters/getters.
Interesting site, I wouldn't implemente something like this in a public
server but sure it's useful.
Regarding the example, looks interesting though it raises s a few doubts
(forgive me if they sound silly):
What's UAP?
This code is part of an inhouse instrument, UAP is artifact of this
instrument, should be:
```
struct MyStruct(Fields...)
{
import std.bitmanip : bitfields;
mixin(makeBitfields!Fields); // <-- Fields instead of UAP
}
```
Where does one define the size for a field using AliasSeq, and in this
example, why does it take 1 bit if the size is not declared anywhere?
I have fields with size equal to one only, you can add another column to
AliasSeq to describe the size
(also, why does it compile when the last field terminates with a comma?)
it's feature of D for convenience
alias Fields = AliasSeq!(
ushort, "field0",
ubyte, "field1",
uint, "field2",
ubyte, "field3",
bool, "field4",
bool, "field5",
bool, "field6",
ubyte, "field7",
);
Why does the switch apply to the remainder of the modulo operation, does
Fields contains indexes to types and names as if it was an array?
May be does, I don't know so I use the remainder.
Re: iterating through members of bitfields
On Friday, 20 January 2017 at 08:13:08 UTC, drug wrote: Something like that https://goo.gl/C4nOqw Because you generate code iterating over AliasSeq you can do almost everything you need - for example generate setters/getters. Interesting site, I wouldn't implemente something like this in a public server but sure it's useful. Regarding the example, looks interesting though it raises s a few doubts (forgive me if they sound silly): What's UAP? Where does one define the size for a field using AliasSeq, and in this example, why does it take 1 bit if the size is not declared anywhere? (also, why does it compile when the last field terminates with a comma?) alias Fields = AliasSeq!( ushort, "field0", ubyte, "field1", uint, "field2", ubyte, "field3", bool, "field4", bool, "field5", bool, "field6", ubyte, "field7", ); Why does the switch apply to the remainder of the modulo operation, does Fields contains indexes to types and names as if it was an array?
Re: iterating through members of bitfields
20.01.2017 04:21, Nestor пишет: On Wednesday, 18 January 2017 at 12:52:56 UTC, drug wrote: I've "solved" the same problem by using AliasSeq to generate bitfields so that for iterating over bitfields I can iterate over alias sequence and mixin code. Not very good but it works. Interesting, could you provide a working example? Something like that https://goo.gl/C4nOqw Because you generate code iterating over AliasSeq you can do almost everything you need - for example generate setters/getters.
Re: iterating through members of bitfields
On Wednesday, 18 January 2017 at 12:52:56 UTC, drug wrote: I've "solved" the same problem by using AliasSeq to generate bitfields so that for iterating over bitfields I can iterate over alias sequence and mixin code. Not very good but it works. Interesting, could you provide a working example?
Re: iterating through members of bitfields
I've "solved" the same problem by using AliasSeq to generate bitfields so that for iterating over bitfields I can iterate over alias sequence and mixin code. Not very good but it works.
Re: iterating through members of bitfields
On Wednesday, 18 January 2017 at 01:15:05 UTC, Ali Çehreli wrote:
Not available but it should be possible to parse the produced
code:
import std.bitmanip;
string makeBitFieldPrinter(string fieldImpl) {
return q{
void printBitFields() const {
import std.stdio: writeln;
writeln("Please improve this function by parsing
fieldImpl. :)");
}
};
}
struct S {
enum myFields = bitfields!(int, "a", 24,
byte, "b", 8);
pragma(msg, "This is the mixed-in bit field
code\n-\n",
myFields, "\n--");
mixin (myFields);
mixin (makeBitFieldPrinter(myFields));
}
void main() {
const s = S();
s.printBitFields();
}
Of course that would depend on the implementation of
bitfields(), which can change without notice.
Ali
Thanks Ali, I was using bitfields according to documentation, but
now I see that way I can't access the mixin string:
struct S {
mixin(bitfields!(
bool, "f1",1,
uint, "f2",4,
uint, "f3",3)
);
}
Re: iterating through members of bitfields
On 01/17/2017 04:37 PM, Nestor wrote:
Hi,
I was just looking at an interesting function from
http://codepad.org/lSDTFd7E :
void printFields(T)(T args) {
auto values = args.tupleof;
size_t max;
size_t temp;
foreach (index, value; values) {
temp = T.tupleof[index].stringof.length;
if (max < temp) max = temp;
}
max += 1;
foreach (index, value; values) {
writefln("%-" ~ to!string(max) ~ "s %s", T.tupleof[index].stringof,
value);
}
}
Can something similar be done for bitfields? I tried running this and I
only get something like this:
_f01_f02_f03 25312
_f04_f05_f06_f07 21129
_f08_f09_f10 53575
_f11_f12_f13_f14 9264
Not available but it should be possible to parse the produced code:
import std.bitmanip;
string makeBitFieldPrinter(string fieldImpl) {
return q{
void printBitFields() const {
import std.stdio: writeln;
writeln("Please improve this function by parsing fieldImpl.
:)");
}
};
}
struct S {
enum myFields = bitfields!(int, "a", 24,
byte, "b", 8);
pragma(msg, "This is the mixed-in bit field code\n-\n",
myFields, "\n--");
mixin (myFields);
mixin (makeBitFieldPrinter(myFields));
}
void main() {
const s = S();
s.printBitFields();
}
Of course that would depend on the implementation of bitfields(), which
can change without notice.
Ali
iterating through members of bitfields
Hi,
I was just looking at an interesting function from
http://codepad.org/lSDTFd7E :
void printFields(T)(T args) {
auto values = args.tupleof;
size_t max;
size_t temp;
foreach (index, value; values) {
temp = T.tupleof[index].stringof.length;
if (max < temp) max = temp;
}
max += 1;
foreach (index, value; values) {
writefln("%-" ~ to!string(max) ~ "s %s",
T.tupleof[index].stringof, value);
}
}
Can something similar be done for bitfields? I tried running this
and I only get something like this:
_f01_f02_f03 25312
_f04_f05_f06_f07 21129
_f08_f09_f10 53575
_f11_f12_f13_f14 9264
Re: BitArray/BitFields - Review
On Thursday, 7 August 2014 at 02:12:20 UTC, H. S. Teoh via Digitalmars-d-learn wrote: Hold on a sec... that's a pull for your own fork of Phobos. You need to submit a pull to the main Phobos repo in order to get it reviewed and merged. :-) Well, no wonder, your pull was submitted against your local fork, not to the main Phobos repo, so nobody knew about it (except Dmitry, apparently). It would help to submit pulls against the main Phobos repo. :-) Also, looks like you made major changes to the code... if it's a complete rewrite, I'd say submit it as a single pull. If it's a collection of many fixes, it's probably better to submit separate pulls so that the easy fixes will get in first while we work out the wrinkles on the more complicated fixes. I did submit it against the original Phobos, and the auto tester picked it up. For something like 3-4 weeks it tried and kept failing over and over again because it couldn't merge it. The reason? It was something like 13 unresolved newlines that didn't match up... or something that I have no idea how I could fix because whitespace is invisible. Later Walter or Andrei (I forget who) complained when they looked at it and wanted me to break it apart into smaller more indivdual bug fixes (since it's hard to tell what i changed as a single blob/replacement) but as a complete re-write and I don't know if I COULD do that... Trust me. I tried. It failed. Eventually I just pulled the request and gave up at that time... Right about the time of the Dconf 2013 I got burned out and got depressed (Probably major changes in meds).
Re: BitArray/BitFields - Review
On Thu, Aug 07, 2014 at 02:04:12AM +, Era Scarecrow via Digitalmars-d-learn wrote: > On Thursday, 7 August 2014 at 01:51:46 UTC, H. S. Teoh via > Digitalmars-d-learn wrote: > >Since this is about contributing to Phobos, probably a better place to ask > >is on the main D forum. > > Yeah posted in my 'what have i missed?' as well... > > >Do you have a pull request? Which one is it? > > https://github.com/rtcvb32/phobos/pull/1 > > From the looks of things it's 4 commits that are merged into a single > request i think... Hold on a sec... that's a pull for your own fork of Phobos. You need to submit a pull to the main Phobos repo in order to get it reviewed and merged. :-) > >There have been a few fixes to std.bitmanip recently, including a > >current PR for adding attributes to some of the functions. Are these > >your PRs, or are you proposing something totally new? If it's > >something totally new, where can we get the code? > > Glancing at the current code, none of my stuff got in. I do a large > number of fixes, so likely a lot of those changes would get thrown > away or integrated... [...] Well, no wonder, your pull was submitted against your local fork, not to the main Phobos repo, so nobody knew about it (except Dmitry, apparently). It would help to submit pulls against the main Phobos repo. :-) Also, looks like you made major changes to the code... if it's a complete rewrite, I'd say submit it as a single pull. If it's a collection of many fixes, it's probably better to submit separate pulls so that the easy fixes will get in first while we work out the wrinkles on the more complicated fixes. T -- Любишь кататься - люби и саночки возить.
Re: BitArray/BitFields - Review
On Thursday, 7 August 2014 at 02:04:13 UTC, Era Scarecrow wrote: On Thursday, 7 August 2014 at 01:51:46 UTC, H. S. Teoh via Digitalmars-d-learn wrote: Do you have a pull request? Which one is it? https://github.com/rtcvb32/phobos/pull/1 From the looks of things it's 4 commits that are merged into a single request i think... Looks like that pull is just the bitfields... but the actual bitmanip one i listed has the whole source.
Re: BitArray/BitFields - Review
On Thursday, 7 August 2014 at 01:51:46 UTC, H. S. Teoh via Digitalmars-d-learn wrote: Since this is about contributing to Phobos, probably a better place to ask is on the main D forum. Yeah posted in my 'what have i missed?' as well... Do you have a pull request? Which one is it? https://github.com/rtcvb32/phobos/pull/1 From the looks of things it's 4 commits that are merged into a single request i think... There have been a few fixes to std.bitmanip recently, including a current PR for adding attributes to some of the functions. Are these your PRs, or are you proposing something totally new? If it's something totally new, where can we get the code? Glancing at the current code, none of my stuff got in. I do a large number of fixes, so likely a lot of those changes would get thrown away or integrated... Knock yourself out... the pull/1 above holds most of the commits and diff/changes to note of. https://github.com/rtcvb32/phobos/blob/master/std/bitmanip.d
Re: BitArray/BitFields - Review
On Thu, Aug 07, 2014 at 01:10:06AM +, Era Scarecrow via Digitalmars-d-learn wrote: > (Moved from: What have I missed?) > > If this is the wrong place to ask these questions I apologize, > getting back into this takes some work. Since this is about contributing to Phobos, probably a better place to ask is on the main D forum. > So I guess I need to ask: Should I try to resume work on the BitManip > library? (So far it seems none of my code has been integrated to > phobos) Do you have a pull request? Which one is it? > Assuming I do, should I try to fix lots of small bugs and make > smaller pulls or should I try to do several at once? When I re-wrote > the BitArray I personally think it is an overall improvement in many > ways, and being a complete re-write you can't just do bug # and > then bug # and then bug... etc etc. > > Also to ask, how many people tried out the rewrite I proposed, and do > they think it was actually an improvement for ease of use, speed, > fewer bugs/issues, etc? There have been a few fixes to std.bitmanip recently, including a current PR for adding attributes to some of the functions. Are these your PRs, or are you proposing something totally new? If it's something totally new, where can we get the code? T -- "Maybe" is a strange word. When mom or dad says it it means "yes", but when my big brothers say it it means "no"! -- PJ jr.
Re: BitArray/BitFields - Review
(Moved from: What have I missed?) If this is the wrong place to ask these questions I apologize, getting back into this takes some work. So I guess I need to ask: Should I try to resume work on the BitManip library? (So far it seems none of my code has been integrated to phobos) Assuming I do, should I try to fix lots of small bugs and make smaller pulls or should I try to do several at once? When I re-wrote the BitArray I personally think it is an overall improvement in many ways, and being a complete re-write you can't just do bug # and then bug # and then bug... etc etc. Also to ask, how many people tried out the rewrite I proposed, and do they think it was actually an improvement for ease of use, speed, fewer bugs/issues, etc?
Re: BitArray/BitFields - Resumed and polishing
07-Jan-2013 00:51, Era Scarecrow пишет: On Thursday, 3 January 2013 at 21:45:24 UTC, Era Scarecrow wrote: K, I'll likely re-work my multi-level huffman algorithmn and a LZW compression, although the LZW wouldn't make use of the more exotic features. Got half the LZW written, but I likely won't get this done for a few days. Nearly done. Got a working LZW, multi-level huffman working, only cleanup/refactoring to do, and a way to save/load the tree structure for external storage. Do I assume you would want me to post it? (Even incomplete and lacking a good portion of documentation/unittests) Sure thing! I'd love to check it out. -- Dmitry Olshansky
Re: BitArray/BitFields - Resumed and polishing
On Thursday, 3 January 2013 at 21:45:24 UTC, Era Scarecrow wrote: K, I'll likely re-work my multi-level huffman algorithmn and a LZW compression, although the LZW wouldn't make use of the more exotic features. Got half the LZW written, but I likely won't get this done for a few days. Nearly done. Got a working LZW, multi-level huffman working, only cleanup/refactoring to do, and a way to save/load the tree structure for external storage. Do I assume you would want me to post it? (Even incomplete and lacking a good portion of documentation/unittests)
Re: BitArray/BitFields - Resumed and polishing
On Thursday, 3 January 2013 at 21:15:19 UTC, Dmitry Olshansky wrote: 04-Jan-2013 00:11, Era Scarecrow wrote: Appending a slice *to* BitArray is perfectly fine as in fact any range of bool (or bit if you like). Any array-like or string-like container has to support appending a range of element type (and insertion for that matter). The table you mention is then an array of BitArray that is sliced (getting a range) and these slices are appended to some other BitArray. BitArrays in this table could also be appended to just fine (so you construct sequences out of others easily). The key point is that *appending a range to container* is fine (and idiomatic) and *slicing is O(1), fast and non-allocating*. So the slice is a non-allocating view of data some data. I can see adding more limitations for that then. I can also see where if you append to a slice it automatically making a new block of memory would be useful as well, as you know you're going to start fresh. Maybe but I can see it being a nasty surprise in a tight loop. Only on the first iteration, unless you do a LOT of slicing & appending on non-compact blocks, but if you're appending to a slice in normal arrays it will dup it anyways (if it doesn't own the following memory) so the behavior doesn't really change. I can make a short test set of functions and post them if you like, doing ranges & slices otherwise might not allow such diversity (simplicity?) in the code. Would be great to put them together as we have implementation details sorted out but have trouble with usage patterns. K, I'll likely re-work my multi-level huffman algorithmn and a LZW compression, although the LZW wouldn't make use of the more exotic features. Got half the LZW written, but I likely won't get this done for a few days. There is an extra rule however, it is the following. If the object in question is not a range and doesn't have opApply but has opSlice() then it slices it first, then again it checks the 2 ways on this slice - as range or opApply. I didn't know that; I know it attempted a slice but not that the slice has to be a range. Likely that needs to be emphasized in the documentation. That's pretty much how std.container tries to work. There is little documentation on the subject though, same note IRC is in TDPL book (highly recommend that one if you don't have it already). Got a copy, in fact this is one of the first prints. I've likely read this book a half dozen times to get a full feel of the language (other than templates which I've learned elsewhere) I agree, but if it's going to be a value type that's heavy on small string optimization with as little referencing as possible, then it has to know what size to depend on, since resizing beyond the Max may not be an option if we take that part out. I meant it's still resizing up to any point, just that it does dup's underlying array on copy (if not small, if small then postblit does nothing). It's questionable to dup on copy but the idea is that it won't be often. If you mean to make type that doesn't resize beyond some maximum (so it's always "small") then indeed having fixed size as template parameter makes more sense. That was the idea. A true value type with no hidden allocation. There are many cases for it, but I think having the BitArray which can allocate has a larger audience than a fixed size. Won't know for sure though, maybe it's the other way around.
Re: BitArray/BitFields - Resumed and polishing
04-Jan-2013 00:11, Era Scarecrow пишет: On Thursday, 3 January 2013 at 15:48:50 UTC, Dmitry Olshansky wrote: 1/3/2013 2:20 PM, Era Scarecrow wrote: Suddenly it won't work and slicing is only a range and can only be used in foreach. No surprise here. Basically container != range over it. It all flows from there. Range doesn't have append nor it owns any data. About foreach see below. Yes, the BitArray container won't pass hasSlicing trait, but it shouldn't as it's meant for ranges. (so in a sense my comment about trying to mimic built-in array applies) And slice can have opIndex and opSlice being a random access range of bool. Hmmm.. shouldn't try to make it as close to an actual array as possible. I feel like I'm missing something very very simple to making it all correct. [snip] >> >> Again I don't think there is a need to append to a slice. Create an >> array out of slice (or in fact any range of bool) then append. > > I want to say you're wrong, I'm thinking heavily in the field where > you would be doing compression or encryption where random access and > appending could be needed at any step. I can see creating a simple table > of the compressed sequences (Say huffman), and then appending the slices > which then greatly simplifies the interface. Appending a slice *to* BitArray is perfectly fine as in fact any range of bool (or bit if you like). Any array-like or string-like container has to support appending a range of element type (and insertion for that matter). The table you mention is then an array of BitArray that is sliced (getting a range) and these slices are appended to some other BitArray. BitArrays in this table could also be appended to just fine (so you construct sequences out of others easily). The key point is that *appending a range to container* is fine (and idiomatic) and *slicing is O(1), fast and non-allocating*. >I can also see where if you > append to a slice it automatically making a new block of memory would be > useful as well, as you know you're going to start fresh. Maybe but I can see it being a nasty surprise in a tight loop. > I can make a > short test set of functions and post them if you like, doing ranges & > slices otherwise might not allow such diversity (simplicity?) in the code. Would be great to put them together as we have implementation details sorted out but have trouble with usage patterns. There is an extra rule however, it is the following. If the object in question is not a range and doesn't have opApply but has opSlice() then it slices it first, then again it checks the 2 ways on this slice - as range or opApply. I didn't know that; I know it attempted a slice but not that the slice has to be a range. Likely that needs to be emphasized in the documentation. That's pretty much how std.container tries to work. There is little documentation on the subject though, same note IRC is in TDPL book (highly recommend that one if you don't have it already). [snip] I'm aware of the container version, and overall if it can just replace BitArray as it is, then we might consider only worrying about a compact version, at which point it would become a template... Might start seeing BitArray!1024 in places (or BitString!1024 ?). I'm not sure if it will gain that much to have templated fixed size bit array over one that just has small optimization. Could be a lot but somehow I don't expect much, that needs some measurement. I agree, but if it's going to be a value type that's heavy on small string optimization with as little referencing as possible, then it has to know what size to depend on, since resizing beyond the max may not be an option if we take that part out. I meant it's still resizing up to any point, just that it does dup's underlying array on copy (if not small, if small then postblit does nothing). It's questionable to dup on copy but the idea is that it won't be often. If you mean to make type that doesn't resize beyond some maximum (so it's always "small") then indeed having fixed size as template parameter makes more sense. -- Dmitry Olshansky
Re: BitArray/BitFields - Resumed and polishing
On Thursday, 3 January 2013 at 15:48:50 UTC, Dmitry Olshansky wrote: 1/3/2013 2:20 PM, Era Scarecrow wrote: Suddenly it won't work and slicing is only a range and can only be used in foreach. No surprise here. Basically container != range over it. It all flows from there. Range doesn't have append nor it owns any data. About foreach see below. Yes, the BitArray container won't pass hasSlicing trait, but it shouldn't as it's meant for ranges. (so in a sense my comment about trying to mimic built-in array applies) And slice can have opIndex and opSlice being a random access range of bool. Hmmm.. shouldn't try to make it as close to an actual array as possible. I feel like I'm missing something very very simple to making it all correct. To help people convert one to the other (exactly where they need it) we can add .dup(?) for the slice that allocates a BitArray and assigns values from range. Correct? You could do appending but likely it would require two functions in the original code (one for a BitArray and one for a slice). Again I don't think there is a need to append to a slice. Create an array out of slice (or in fact any range of bool) then append. I want to say you're wrong, I'm thinking heavily in the field where you would be doing compression or encryption where random access and appending could be needed at any step. I can see creating a simple table of the compressed sequences (Say huffman), and then appending the slices which then greatly simplifies the interface. I can also see where if you append to a slice it automatically making a new block of memory would be useful as well, as you know you're going to start fresh. I can make a short test set of functions and post them if you like, doing ranges & slices otherwise might not allow such diversity (simplicity?) in the code. If it supports a opAssign to handle that now you have to take care of all opAssign's as well (like C++, once you handle one portion of it and opCast, you handle them all). Yes, I'm afraid that for optimal speed they both have to be implemented. The version for BitArray can just forward to the one for slice over the whole of it. Or there could be a common template function that handles all of bit-ops over [a, b) portions of BitArrays. Everything else then forwards to it. Does that mean we might be able to drop opApply? Hmmm... Depends on if we have enough implemented so the range accepts it. I'll glance over std.range. Yes, it's got to be a range to work like this and then opApply is useless. Maybe. Foreach if I remember right worked three different ways, and selected whichever one worked. opApply, front/pop/empty, and array (opIndex access). If enough is implemented that it recognizes it as an array then opApply can be removed. There are 2 ways: range or opApply. How built-in arrays are done is up to compiler, there is no way to tap into it from user level. There is an extra rule however, it is the following. If the object in question is not a range and doesn't have opApply but has opSlice() then it slices it first, then again it checks the 2 ways on this slice - as range or opApply. I didn't know that; I know it attempted a slice but not that the slice has to be a range. Likely that needs to be emphasized in the documentation. A quick tests shows that currently isn't the case. Really depends on the use case. I'm guessing there's enough call for the 64bit small packed bitarray that justifies it, otherwise it would be better to throw it out. As you mention later, separating them does seem like a better idea. I've meant the fact that it has to preserve current std lib behavior *and* has small string optimization that makes it overly painful and partially defeats the optimization (by requiring pointless compact->big conversions on slice etc.). We could always 'dup' on slice instead, but then you can't use references on it, at which point it's a value type. Dup on slice is very bad. Slice in container world (I'm looking at std.container and this not likely to change) is a view of the same data, thus it's *not* a new container on its own. Hmmm. Being a pure value type then a separate range makes more sense to use. hmmm.. Either would need some code duplication, or template to turn off/swap small string optimization. But separating them does seem like a good idea. I'd expect a fair chunk of code to be split off into free functions, then both containers would make use of them. Now note that there is also std.container Array!bool that has reference semantics and got to be doing bit packing... it could potentially take place of big BitArray mentioned. I'm aware of the container version, and overall if it can just replace BitArray as it is, then we might consider only worrying about a compact version, at which point it would become a template... Might start seeing BitArray!1024 in places (or BitString!1024 ?). I'm n
Re: BitArray/BitFields - Resumed and polishing
1/3/2013 2:20 PM, Era Scarecrow пишет:
On Thursday, 3 January 2013 at 07:57:46 UTC, Dmitry Olshansky wrote:
1/3/2013 6:05 AM, Era Scarecrow wrote:
Hm, I'd think that having Slice type be:
BitArraySlice{
BitArray* bp;
size_t start, end;
// all else forwards to the pointed array
}
should work avoiding the most of code duplication. With any luck
inliner will expand all of this wrapping. To enable bulk mode operations:
void opOpSliceAssign(BitArraySlice rhs)
{//has all the data to do it
bulkOp(bp, start, end, rhs.bp, rhs.start, rhs.end);
}
then it's a question of bit of refactoring & tweaking of array bulks ops.
Then the only problem left is slice invalidation and original array
going out of scope.
I know we've had this discussion before. So let's assume you do
slicing this way. So what happens when...
BitArray ba = [0,1,1,0];
ba = ba[1 .. $-1]; // ba is not a BitArraySlice
Suddenly it won't work and slicing is only a range and can only be
used in foreach.
No surprise here. Basically container != range over it. It all flows
from there. Range doesn't have append nor it owns any data.
About foreach see below. Yes, the BitArray container won't pass
hasSlicing trait, but it shouldn't as it's meant for ranges.
(so in a sense my comment about trying to mimic built-in array applies)
And slice can have opIndex and opSlice being a random access range of bool.
To help people convert one to the other (exactly where they need it) we
can add .dup(?) for the slice that allocates a BitArray and assigns
values from range.
Correct? You could do appending but likely it would
require two functions in the original code (one for a BitArray and one
for a slice).
Again I don't think there is a need to append to a slice. Create an
array out of slice (or in fact any range of bool) then append.
It it supports a opAssign to handle that now you have to
take care of all opAssign's as well (like C++, once you handle one
portion of it and opCast, you handle them all).
Yes, I'm afraid that for optimal speed they both have to be implemented.
The version for BitArray can just forward to the one for slice over the
whole of it. Or there could be a common template function that handles
all of bit-ops over [a, b) portions of BitArrays. Everything else then
forwards to it.
Does that mean we might be able to drop opApply? Hmmm... Depends on
if we have enough implemented so the range accepts it. I'll glance
over std.range.
Yes, it's got to be a range to work like this and then opApply is
useless.
Maybe. Foreach if I remember right worked three different ways, and
selected whichever one worked. opApply, front/pop/empty, and array
(opIndex access). If enough is implemented that it recognizes it as an
array then opApply can be removed.
There are 2 ways: range or opApply. How built-in arrays are done is up
to compiler, there is no way to tap into it from user level.
There is an extra rule however, it is the following. If the object in
question is not a range and doesn't have opApply but has opSlice() then
it slices it first, then again it checks the 2 ways on this slice - as
range or opApply.
A quick tests shows that currently isn't the case.
Really depends on the use case. I'm guessing there's enough call for
the 64bit small packed bitarray that justifies it, otherwise it would
be better to throw it out. As you mention later, separating them does
seem like a better idea.
I've meant the fact that it has to preserve current std lib behavior
*and* has small string optimization that makes it overly painful and
partially defeats the optimization (by requiring pointless
compact->big conversions on slice etc.).
We could always 'dup' on slice instead, but then you can't use
references on it, at which point it's a value type.
Dup on slice is very bad. Slice in container world (I'm looking at
std.container and this not likely to change) is a view of the same data,
thus it's *not* a new container on its own.
Hmmm. Being a pure
value type then a separate range makes more sense to use.
hmmm.. Either would need some code duplication, or template to turn
off/swap small string optimization. But separating them does seem
like a good idea.
I'd expect a fair chunk of code to be split off into free functions,
then both containers would make use of them.
Now note that there is also std.container Array!bool that has
reference semantics and got to be doing bit packing... it could
potentially take place of big BitArray mentioned.
I'm aware of the container version, and overall if it can just replace
BitArray as it is, then we might consider only worrying about a compact
version, at which point it would become a template... Might start seeing
BitArray!1024 in places (or BitString!1024 ?).
I'm not sure if it will gain that much to have templated fixed size bit
array over one that just has small optimization. Could be a lot but
somehow I don't expect much, that needs some measuremen
Re: BitArray/BitFields - Resumed and polishing
On Thursday, 3 January 2013 at 07:57:46 UTC, Dmitry Olshansky
wrote:
1/3/2013 6:05 AM, Era Scarecrow wrote:
Hm, I'd think that having Slice type be:
BitArraySlice{
BitArray* bp;
size_t start, end;
// all else forwards to the pointed array
}
should work avoiding the most of code duplication. With any
luck inliner will expand all of this wrapping. To enable bulk
mode operations:
void opOpSliceAssign(BitArraySlice rhs)
{//has all the data to do it
bulkOp(bp, start, end, rhs.bp, rhs.start, rhs.end);
}
then it's a question of bit of refactoring & tweaking of array
bulks ops.
Then the only problem left is slice invalidation and original
array going out of scope.
I know we've had this discussion before. So let's assume you do
slicing this way. So what happens when...
BitArray ba = [0,1,1,0];
ba = ba[1 .. $-1]; // ba is not a BitArraySlice
Suddenly it won't work and slicing is only a range and can only
be used in foreach. Correct? You could do appending but likely it
would require two functions in the original code (one for a
BitArray and one for a slice). It it supports a opAssign to
handle that now you have to take care of all opAssign's as well
(like C++, once you handle one portion of it and opCast, you
handle them all).
Does that mean we might be able to drop opApply? Hmmm...
Depends on if we have enough implemented so the range accepts
it. I'll glance over std.range.
Yes, it's got to be a range to work like this and then opApply
is useless.
Maybe. Foreach if I remember right worked three different ways,
and selected whichever one worked. opApply, front/pop/empty, and
array (opIndex access). If enough is implemented that it
recognizes it as an array then opApply can be removed.
A quick tests shows that currently isn't the case.
Really depends on the use case. I'm guessing there's enough
call for the 64bit small packed bitarray that justifies it,
otherwise it would be better to throw it out. As you mention
later, separating them does seem like a better idea.
I've meant the fact that it has to preserve current std lib
behavior *and* has small string optimization that makes it
overly painful and partially defeats the optimization (by
requiring pointless compact->big conversions on slice etc.).
We could always 'dup' on slice instead, but then you can't use
references on it, at which point it's a value type. Hmmm. Being a
pure value type then a separate range makes more sense to use.
hmmm.. Either would need some code duplication, or template to
turn off/swap small string optimization. But separating them
does seem like a good idea.
I'd expect a fair chunk of code to be split off into free
functions, then both containers would make use of them.
Now note that there is also std.container Array!bool that has
reference semantics and got to be doing bit packing... it could
potentially take place of big BitArray mentioned.
I'm aware of the container version, and overall if it can just
replace BitArray as it is, then we might consider only worrying
about a compact version, at which point it would become a
template... Might start seeing BitArray!1024 in places (or
BitString!1024 ?).
Re: BitArray/BitFields - Resumed and polishing
1/3/2013 6:05 AM, Era Scarecrow пишет:
On Wednesday, 2 January 2013 at 21:00:38 UTC, Dmitry Olshansky wrote:
12/31/2012 9:35 PM, Era Scarecrow пишет:
Personally I believe that if we introduce a slice of a BitArray as a
separate range type that represents a view of array (but can't be
appended to, etc. it's just a RA range with slicing).
Could do that I suppose, but then either exact length or
append/alignment optimizations may go out the window if we remove some
of those as options. To support those making slices part of the main
type was easy enough. But the other issues still have to be addressed
(that's mentioned below)
const BitArray x = BitArray(32);
func(x);
Then here x is passed either by ref or a copy (depending on func).
yeah... assuming func returned a struct of...
struct S {
BitArray x;
//other stuff
}
const(BitArray) func(const BitArray s);
in the case it's small string optimization and the original string
gets allocated OR gets passed outside the original function that made
the BitArray. So small string if possible, convert to ref and slice it,
or dup it. not 100% ref in all cases but pretty close.
Would the function get passed the original compact buffer? Copy of x
or a dup? May not be so much an issue. However...
BitArray x = BitArray(32);
const y = x[]; //slice
Then y has type BitArraySlice and references x.
Agreed, although I'm still iffy about a separate slice as a range.
Could do the range just to give it limitations, but seems like a
headache to do less and extra code to manage.
Current code I'm writing converts (if possible) the BitArray to a
allocated type, then passes that slice to y.
Now if y points to the actual compact buffer and we do the following...
x.length = 256; //allocates if it was compact
Although y will have const access the data instead of a compact
array it's a pointer to an array and broken.
Then IMO that should be a slice invalidation (akin to c++ iterator
invalidation). Depending on how slice is implemented it could avoid
being invalidated in this case but in some others it surely will (e.g.
shrinking).
Maybe, with the small string optimization (no allocation) it isn't so
much an easy option. That's what this is about. Say it uses the compact
(fixed string) and in opSlice...
BitArray {
bool isCompact;
bool canExpand; //represents owner for slices or compact.
union {
size_t[] normal;
size_t[2] compact;
}
BitArray opSlice() {
BitArray ba = this;
ba.canExpand = false;
if (isCompact) {
ba.isCompact = false;
ba.normal = cast(size_t[]) this.compact[0 .. $];
}
return ba;
}
}
This is where the allocation could cause a problem as the slice could
be referring to stack memory at which all the data could be duds. Worse
if you overwrite that data suddenly the allocated memory could point to
something else! I think it's safe to say that's a bad idea.
Hm, I'd think that having Slice type be:
BitArraySlice{
BitArray* bp;
size_t start, end;
// all else forwards to the pointed array
}
should work avoiding the most of code duplication. With any luck inliner
will expand all of this wrapping. To enable bulk mode operations:
void opOpSliceAssign(BitArraySlice rhs)
{//has all the data to do it
bulkOp(bp, start, end, rhs.bp, rhs.start, rhs.end);
}
then it's a question of bit of refactoring & tweaking of array bulks ops.
Then the only problem left is slice invalidation and original array
going out of scope.
If during the x call it
You mean x[] call i.e. opSlice() call?
well both this(this) and opSlice() would be called at different times
so they would have different meanings (copying vs slicing).
Seems like an overkill and semantically bad as I totally expect that
the following to be true for any Array-like container:
auto cont = ...;
auto range = cont[];
range[0] = 1;
assert(cont[0] == 1);
Also:
foreach(v; x) --> foreach(v; x[]) if x defines opSlice
however since BitArray defines opApply it's called instead so this one
is probably OK.
Does that mean we might be able to drop opApply? Hmmm... Depends on if
we have enough implemented so the range accepts it. I'll glance over
std.range.
Yes, it's got to be a range to work like this and then opApply is useless.
reallocated then y would work fine no matter what in that case. If x
can't reallocate it, then the issue remains but is much smaller than
before, most likely a dup would be safest.
Thoughts? Questions? Ideas?
The link to the latest code would be cool ;)
https://github.com/rtcvb32/phobos/blob/BitArray-Updates/std/bitmanip.d
There's a merge issue due to having tried to keep the bitfields and
bitarray separated; That seems to have made more problems than
solutions. Working on it but may have to wait until I've read my Git
book when it arrives before I
Re: BitArray/BitFields - Resumed and polishing
On Wednesday, 2 January 2013 at 21:00:38 UTC, Dmitry Olshansky
wrote:
12/31/2012 9:35 PM, Era Scarecrow пишет:
Personally I believe that if we introduce a slice of a BitArray
as a separate range type that represents a view of array (but
can't be appended to, etc. it's just a RA range with slicing).
Could do that I suppose, but then either exact length or
append/alignment optimizations may go out the window if we remove
some of those as options. To support those making slices part of
the main type was easy enough. But the other issues still have to
be addressed (that's mentioned below)
const BitArray x = BitArray(32);
func(x);
Then here x is passed either by ref or a copy (depending on
func).
yeah... assuming func returned a struct of...
struct S {
BitArray x;
//other stuff
}
const(BitArray) func(const BitArray s);
in the case it's small string optimization and the original
string gets allocated OR gets passed outside the original
function that made the BitArray. So small string if possible,
convert to ref and slice it, or dup it. not 100% ref in all cases
but pretty close.
Would the function get passed the original compact buffer?
Copy of x or a dup? May not be so much an issue. However...
BitArray x = BitArray(32);
const y = x[]; //slice
Then y has type BitArraySlice and references x.
Agreed, although I'm still iffy about a separate slice as a
range. Could do the range just to give it limitations, but seems
like a headache to do less and extra code to manage.
Current code I'm writing converts (if possible) the BitArray to
a allocated type, then passes that slice to y.
Now if y points to the actual compact buffer and we do the
following...
x.length = 256; //allocates if it was compact
Although y will have const access the data instead of a
compact array it's a pointer to an array and broken.
Then IMO that should be a slice invalidation (akin to c++
iterator invalidation). Depending on how slice is implemented
it could avoid being invalidated in this case but in some
others it surely will (e.g. shrinking).
Maybe, with the small string optimization (no allocation) it
isn't so much an easy option. That's what this is about. Say it
uses the compact (fixed string) and in opSlice...
BitArray {
bool isCompact;
bool canExpand; //represents owner for slices or compact.
union {
size_t[] normal;
size_t[2] compact;
}
BitArray opSlice() {
BitArray ba = this;
ba.canExpand = false;
if (isCompact) {
ba.isCompact = false;
ba.normal = cast(size_t[]) this.compact[0 .. $];
}
return ba;
}
}
This is where the allocation could cause a problem as the slice
could be referring to stack memory at which all the data could be
duds. Worse if you overwrite that data suddenly the allocated
memory could point to something else! I think it's safe to say
that's a bad idea.
If during the x call it
You mean x[] call i.e. opSlice() call?
well both this(this) and opSlice() would be called at different
times so they would have different meanings (copying vs slicing).
Seems like an overkill and semantically bad as I totally expect
that the following to be true for any Array-like container:
auto cont = ...;
auto range = cont[];
range[0] = 1;
assert(cont[0] == 1);
Also:
foreach(v; x) --> foreach(v; x[]) if x defines opSlice
however since BitArray defines opApply it's called instead so
this one is probably OK.
Does that mean we might be able to drop opApply? Hmmm... Depends
on if we have enough implemented so the range accepts it. I'll
glance over std.range.
reallocated then y would work fine no matter what in that
case. If x can't reallocate it, then the issue remains but is
much smaller than before, most likely a dup would be safest.
Thoughts? Questions? Ideas?
The link to the latest code would be cool ;)
https://github.com/rtcvb32/phobos/blob/BitArray-Updates/std/bitmanip.d
There's a merge issue due to having tried to keep the bitfields
and bitarray separated; That seems to have made more problems
than solutions. Working on it but may have to wait until I've
read my Git book when it arrives before I understand this all.
I'm thinking that the main problem is trying to mimic built-in
arrays.
Not really, it's trying to do small string optimization. I
suppose if this was done as a class instead most of these
problems could/would go away.
They are not ordinary containers in that they easily combine
slice and container that is (in fact) partially hidden in
run-time & GC implementation.
The fact that combination of language features and run-time
support makes it easy shouldn't encourage other to go this path
in the library.
For one thing this way a small string optimization is not
achievable because of the many slices that have to reference
the data
Re: BitArray/BitFields - Resumed and polishing
12/31/2012 9:35 PM, Era Scarecrow пишет: As BitArray is coming back up and my resumed work I'll comment a few questions and suggestions and go from there. I'll polish up the code and try to resubmit it. Yay! On Saturday, 28 July 2012 at 21:07:31 UTC, Jonathan M Davis wrote: I would point out that while hasSlicing doesn't currently check for it, if opSlice doesn't return a type which is assignable to the original range, it won't work in a lot of Phobos functions. I keep meaning to bring that up for discussion in the main newsgroup. I'd argue that hasSlicing really be changed from Hmmm.. Well Since the 'sometimes ref' as discussed won't seem to work well from before I'm considering to put the following two rules into effect. 1) If it's an allocated block, it stays allocated. 2) If you dup a BitArray and it's small enough to be compact, it converts. 3) If it's a small/compact array and you give out a slice, it converts the original block to dynamic before returning the new slice. With 1 & 2, reserved and length work a little differently, more ref friendly. With 3 the only issue comes up with if it's const, or a local variable. Personally I believe that if we introduce a slice of a BitArray as a separate range type that represents a view of array (but can't be appended to, etc. it's just a RA range with slicing). const BitArray x = BitArray(32); func(x); Then here x is passed either by ref or a copy (depending on func). Would the function get passed the original compact buffer? Copy of x or a dup? May not be so much an issue. However... BitArray x = BitArray(32); const y = x[]; //slice Then y has type BitArraySlice and references x. Now if y points to the actual compact buffer and we do the following... x.length = 256; //allocates if it was compact Although y will have const access the data instead of a compact array it's a pointer to an array and broken. Then IMO that should be a slice invalidation (akin to c++ iterator invalidation). Depending on how slice is implemented it could avoid being invalidated in this case but in some others it surely will (e.g. shrinking). If during the x call it You mean x[] call i.e. opSlice() call? Seems like an overkill and semantically bad as I totally expect that the following to be true for any Array-like container: auto cont = ...; auto range = cont[]; range[0] = 1; assert(cont[0] == 1); Also: foreach(v; x) --> foreach(v; x[]) if x defines opSlice however since BitArray defines opApply it's called instead so this one is probably OK. reallocated then y would work fine no matter what in that case. If x can't reallocate it, then the issue remains but is much smaller than before, most likely a dup would be safest. Thoughts? Questions? Ideas? The link to the latest code would be cool ;) I'm thinking that the main problem is trying to mimic built-in arrays. They are not ordinary containers in that they easily combine slice and container that is (in fact) partially hidden in run-time & GC implementation. The fact that combination of language features and run-time support makes it easy shouldn't encourage other to go this path in the library. For one thing this way a small string optimization is not achievable because of the many slices that have to reference the data packed in _small_ chunk. Then whenever original array changes (and becomes not small) any other slice to it have to somehow reflect this change. And it's hard if slices internally are exactly the same as original (if the same type). ... Now that I tested the current behavior that we shouldn't break a lot. Clearly current BitArray is old and rusty D1 design. BitArray a, b, c; //the interesting thing is that BitArray(32) doesn't construct BitArray with length 32 but some explosive garbage !! c.length = 512; a.length = 32; assert(a.length == 32); b = a; b[0] = true; //this one is bad as it means both a & b has to reference the same data assert(a[0] == 1); b ~= c; b[1] = 1; //the next fails for me (it also may not fail depending on c's length) assert(a[1] == 1); Currently I think that D container design have to be extended to include 2 kinds of containers: -small containers, values type a-la C++ STL these all use small container optimization (as they can cleanly) -big heavy-duty ones, these have reference semantics and tuned for large sets of values Then the proposed way out is to make 2 containers: - current BitArray to always have reference semantics (both asserts in the above always pass); - and BitString or BitVector to be small value semantic array that is always copied/duped on assign, these should be passed by ref or by range/slice. That's was lengthy but what do you think? And it seems like we'd need to bring this last topic to general D NG. -- Dmitry Olshansky
BitArray/BitFields - Resumed and polishing
As BitArray is coming back up and my resumed work I'll comment a few questions and suggestions and go from there. I'll polish up the code and try to resubmit it. On Saturday, 28 July 2012 at 21:07:31 UTC, Jonathan M Davis wrote: I would point out that while hasSlicing doesn't currently check for it, if opSlice doesn't return a type which is assignable to the original range, it won't work in a lot of Phobos functions. I keep meaning to bring that up for discussion in the main newsgroup. I'd argue that hasSlicing really be changed from Hmmm.. Well Since the 'sometimes ref' as discussed won't seem to work well from before I'm considering to put the following two rules into effect. 1) If it's an allocated block, it stays allocated. 2) If you dup a BitArray and it's small enough to be compact, it converts. 3) If it's a small/compact array and you give out a slice, it converts the original block to dynamic before returning the new slice. With 1 & 2, reserved and length work a little differently, more ref friendly. With 3 the only issue comes up with if it's const, or a local variable. const BitArray x = BitArray(32); func(x); Would the function get passed the original compact buffer? Copy of x or a dup? May not be so much an issue. However... BitArray x = BitArray(32); const y = x[]; //slice Now if y points to the actual compact buffer and we do the following... x.length = 256; //allocates if it was compact Although y will have const access the data instead of a compact array it's a pointer to an array and broken. If during the x call it reallocated then y would work fine no matter what in that case. If x can't reallocate it, then the issue remains but is much smaller than before, most likely a dup would be safest. Thoughts? Questions? Ideas?
Re: Why must bitfields sum to a multiple of a byte?
On Thursday, 2 August 2012 at 14:52:58 UTC, Andrei Alexandrescu wrote: On 8/2/12 9:48 AM, monarch_dodra wrote: By forcing the developer to chose the bitfield size (32 or 64), you ARE forcing him to make a choice dependent on the machine's characteristics. I think that's backwards. I think specifying bitfields, you're already going really low level; meaning you need explicit and full control. As for portability, if the size is specified, it comes down to endinness or order of the fields. Zlib header: http://tools.ietf.org/html/rfc1950 A zlib stream has the following structure: CMF, FLaG CMF: bits 0 to 3 CM Compression method bits 4 to 7 CINFO Compression info FLaG: bits 0 to 4 FCHECK (check bits for CMF and FLG) bit 5 FDICT (preset dictionary) bits 6 to 7 FLEVEL (compression level) This easily becomes: //assumes small-endian mixin(bitfields( ubyte, "CM", 4, ubyte, "CINFO", 4, ubyte, "FCHECK", 5, ubyte, "FDICT", 1, ubyte, "FLEVEL", 2)); //should be exactly 16 bits Now if a typo was done (wrong number of bits) or endianness is questionable, this becomes completely different as the fields could be as much as 3-7 bytes off (24 bits, or worse if it assumes 64bits, 56 bits off), or cover a much larger area than it should for the bits. This is unacceptable, especially if you need to get low level with the code.
Re: Why must bitfields sum to a multiple of a byte?
On 8/2/12 9:48 AM, monarch_dodra wrote: On Thursday, 2 August 2012 at 12:38:10 UTC, Andrei Alexandrescu wrote: On 8/2/12 5:26 AM, monarch_dodra wrote: One of the *big* reasons I'm against having a hand chosen padding, is that the implementation *should* be able to find out what the most efficient padding is on the current machine (could be 32 on some, could be 64 on some) In my neck of the woods they call that "non-portability". If your code is dependent on the machine's characteristics you use version() and whatnot. Well, isn't that the entire point: Making your code NOT dependent on the machine's characteristics? By forcing the developer to chose the bitfield size (32 or 64), you ARE forcing him to make a choice dependent on the machine's characteristics. I think that's backwards. Andrei
Re: Why must bitfields sum to a multiple of a byte?
On Thursday, 2 August 2012 at 12:38:10 UTC, Andrei Alexandrescu wrote: On 8/2/12 5:26 AM, monarch_dodra wrote: One of the *big* reasons I'm against having a hand chosen padding, is that the implementation *should* be able to find out what the most efficient padding is on the current machine (could be 32 on some, could be 64 on some) In my neck of the woods they call that "non-portability". If your code is dependent on the machine's characteristics you use version() and whatnot. Well, isn't that the entire point: Making your code NOT dependent on the machine's characteristics? By forcing the developer to chose the bitfield size (32 or 64), you ARE forcing him to make a choice dependent on the machine's characteristics. The developer just knows how he wants to pack his bits, not how he wants to pad them. Why should the developer be burdened with figuring out what the optimal size of his bitfield should be? By leaving the field blank, *that* guarantees portability.
bitfields - 4425 bells & whistles
Following from issue list:
bearophile_hugs 2010-10-04 18:16:44 PDT
Another possible feature is to make std.bitmanip.bitfields
generate two
versions of the code, that get compiled conditionally according
to the CPU
endianess:
static if (std.system.endian == std.system.Endian.BigEndian) {
...
} else {
...
}
Having it endian specific brings up a couple questions.
Which endian is 'correct'? Resolutions could be...
a) Both are correct (Leave as is)
b) big/little is correct and should always convert to the other
(which one?)
c) Specify correct type as a flag, then swaps for the other in
generated code
Second, which would be the best approach?
a) swap bytes in a temporary, modify the temporary, replace
storage? (In every function)
b) use current endianness, then prepping saving/loading have it
swap? (very unlikely)
c) use ubyte array and use shifting on each byte (small Endian,
also allows for odd byte sizes, not very likely, but possible)
I know an instruction for the Pentium system (686+?) bswap will
swap the appropriate bytes as a conversion and takes a single
cycle, using assembler that can be incorporated assuming it's
ready for it (course than the template would be updated more
likely and not the bitfield template).
Re: Why must bitfields sum to a multiple of a byte?
On Thursday, 2 August 2012 at 12:35:20 UTC, Andrei Alexandrescu wrote: Please don't. The effort on the programmer side is virtually nil, and keeps things in check. In no case would the use of bitfields() be so intensive that the bloat of one line gets any significance.> If you're using a template or something to fill in the sizes, then having to calculate the remainder could be an annoyance; but those cases would be small in number. I'll agree, and it's best leaving it as it is. BTW, Wasn't there a new/reserved type of cent/ucent (128bit)?
Re: Why must bitfields sum to a multiple of a byte?
On 8/2/12 5:26 AM, monarch_dodra wrote: One of the *big* reasons I'm against having a hand chosen padding, is that the implementation *should* be able to find out what the most efficient padding is on the current machine (could be 32 on some, could be 64 on some) In my neck of the woods they call that "non-portability". If your code is dependent on the machine's characteristics you use version() and whatnot. Andrei
Re: Why must bitfields sum to a multiple of a byte?
On 8/2/12 5:14 AM, Era Scarecrow wrote:
On Thursday, 2 August 2012 at 09:03:54 UTC, monarch_dodra wrote:
I had an (implementation) question for you: Does the implementation
actually require knowing what the size of the padding is?
eg:
struct A
{
int a;
mixin(bitfields!(
uint, "x", 2,
int, "y", 3,
ulong, "", 3 // <- This line right there
));
}
It that highlighted line really mandatory?
I'm fine with having it optional, in case I'd want to have, say, a 59
bit padding, but can't the implementation figure it out on it's own?
The original code has it set that way, why? Perhaps so you are aware and
actually have in place where all the bits are assigned (even if you
aren't using them); Be horrible if you used accidently 33 bits and it
extended to 64 without telling you (Wouldn't it?).
Yes, that's the intent. The user must define exactly how an entire
ubyte/ushort/uint/ulong is filled, otherwise ambiguities and bugs are
soon to arrive.
However, having it fill the size in and ignore the last x bits wouldn't
be too hard to do, I've been wondering if I should remove it.
Please don't. The effort on the programmer side is virtually nil, and
keeps things in check. In no case would the use of bitfields() be so
intensive that the bloat of one line gets any significance.
Andrei
bitfields - Padding needed?
On Thursday, 2 August 2012 at 09:26:04 UTC, monarch_dodra wrote: Well, I was just trying to figure out the rationale: The most obvious one for me being "it is much easier on the implementation". Since the template is recursive and at the end after bit counting would know how much it needed, that doesn't seem right; far more likely just to be explicit. One of the *big* reasons I'm against having a hand chosen padding, is that the implementation *should* be able to find out what the most efficient padding is on the current machine (could be 32 on some, could be 64 on some) If your using bitfields, then you are going for space, and to be as small as reasonably possible. Especially important for packets of information like headers for compression, and making it compatible with C/C++'s bitpacking. That said, something that could fix the above "problem" could be: *Bitfields are automatically padded if the final field is not a "padding field". Workable **Padding size is implementation chosen. I assume you mean by word size (size_t), meaning always 32/64bit. In that case many applicable cases would go away and be useless. *If the final field is a "padding field", then the total size must be 8/16/32/64. EG: //Case 1 bitfields!( bool, "x",1, uint, "",3, //Interfield padding bool, "y",1 ) //Fine, implementation chosen bitfield size It would go with a ubyte as is likely obvious, although any of the types would work. //Case 2 bitfields!( bool, "x",1, uint, "",3, //Interfield padding bool, "y",1 ulong, "", 59, //Pad to 64 ) //Fine, imposed 64 bit //Case 3 bitfields!( bool, "x",1, uint, "",3, //Interfield padding bool, "y",1 ulong, "", 32, //Pad to 37 ) //ERROR: Padding requests the bitfield to be 37 bits longs But I'd say that's another development anyways, if we ever decide to go this way. In the end, either explicit in size, or let it round up to the size it can accept. If you let it decide, then padding would be treated as though it's a variable (but isn't), so... bitfields!( bool, "x",1, uint, "",3, //Interfield padding bool, "y",1 ulong, "", 5, ) the total size is 9bits, the padding forces it to 16bit afterwards. In cases like this it could easily be abused or leave it in a confusing state; So likely the padding would have to be missing (and assumed) or explicit in size. So previous one would err, while: bitfields!( bool, "x",1, uint, "",3, //Interfield padding bool, "y",1, // void, "", 4 //implied by missing, if padded and final size not ^2 would statically assert. )
Re: Why must bitfields sum to a multiple of a byte?
On Thursday, 2 August 2012 at 09:14:15 UTC, Era Scarecrow wrote:
On Thursday, 2 August 2012 at 09:03:54 UTC, monarch_dodra wrote:
I had an (implementation) question for you: Does the
implementation actually require knowing what the size of the
padding is?
eg:
struct A
{
int a;
mixin(bitfields!(
uint, "x",2,
int, "y",3,
ulong, "",3 // <- This line right there
));
}
It that highlighted line really mandatory?
I'm fine with having it optional, in case I'd want to have,
say, a 59 bit padding, but can't the implementation figure it
out on it's own?
The original code has it set that way, why? Perhaps so you are
aware and actually have in place where all the bits are
assigned (even if you aren't using them); Be horrible if you
used accidently 33 bits and it extended to 64 without telling
you (Wouldn't it?).
However, having it fill the size in and ignore the last x bits
wouldn't be too hard to do, I've been wondering if I should
remove it.
Well, I was just trying to figure out the rationale: The most
obvious one for me being "it is much easier on the
implementation".
One of the *big* reasons I'm against having a hand chosen
padding, is that the implementation *should* be able to find out
what the most efficient padding is on the current machine (could
be 32 on some, could be 64 on some)
That said, something that could fix the above "problem" could be:
*Bitfields are automatically padded if the final field is not a
"padding field".
**Padding size is implementation chosen.
*If the final field is a "padding field", then the total size
must be 8/16/32/64.
EG:
//Case 1
bitfields!(
bool, "x",1,
uint, "",3, //Interfield padding
bool, "y",1
)
//Fine, implementation chosen bitfield size
//Case 2
bitfields!(
bool, "x",1,
uint, "",3, //Interfield padding
bool, "y",1
ulong, "", 59, //Pad to 64
)
//Fine, imposed 64 bit
//Case 3
bitfields!(
bool, "x",1,
uint, "",3, //Interfield padding
bool, "y",1
ulong, "", 32, //Pad to 37
)
//ERROR: Padding requests the bitfield to be 37 bits longs
But I'd say that's another development anyways, if we ever decide
to go this way.
Re: Why must bitfields sum to a multiple of a byte?
On Thursday, 2 August 2012 at 09:03:54 UTC, monarch_dodra wrote:
I had an (implementation) question for you: Does the
implementation actually require knowing what the size of the
padding is?
eg:
struct A
{
int a;
mixin(bitfields!(
uint, "x",2,
int, "y",3,
ulong, "",3 // <- This line right there
));
}
It that highlighted line really mandatory?
I'm fine with having it optional, in case I'd want to have,
say, a 59 bit padding, but can't the implementation figure it
out on it's own?
The original code has it set that way, why? Perhaps so you are
aware and actually have in place where all the bits are assigned
(even if you aren't using them); Be horrible if you used
accidently 33 bits and it extended to 64 without telling you
(Wouldn't it?).
However, having it fill the size in and ignore the last x bits
wouldn't be too hard to do, I've been wondering if I should
remove it.
Re: Why must bitfields sum to a multiple of a byte?
On Wednesday, 1 August 2012 at 07:24:09 UTC, Era Scarecrow wrote:
On Tuesday, 31 July 2012 at 20:41:55 UTC, Dmitry Olshansky
wrote:
Great to see things moving. Could you please do a separate
pull for bitfields it should get merged easier and it seems
like a small but important bugfix.
https://github.com/rtcvb32/phobos/commit/620ba57cc0a860245a2bf03f7b7f5d6a1bb58312
I've updated the next update in my bitfields branch. All
unittests pass for me.
I had an (implementation) question for you:
Does the implementation actually require knowing what the size of
the padding is?
eg:
struct A
{
int a;
mixin(bitfields!(
uint, "x",2,
int, "y",3,
ulong, "",3 // <- This line right there
));
}
It that highlighted line really mandatory?
I'm fine with having it optional, in case I'd want to have, say,
a 59 bit padding, but can't the implementation figure it out on
it's own?
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 20:41:55 UTC, Dmitry Olshansky wrote: Great to see things moving. Could you please do a separate pull for bitfields it should get merged easier and it seems like a small but important bugfix. https://github.com/rtcvb32/phobos/commit/620ba57cc0a860245a2bf03f7b7f5d6a1bb58312 I've updated the next update in my bitfields branch. All unittests pass for me.
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 20:41:55 UTC, Dmitry Olshansky wrote: On 31-Jul-12 22:21, Era Scarecrow wrote: Well curiously it was easier to fix than I thought (a line for a static if, and a modification of the masking)... Was there any other bugs that come to mind? Anything of consequence? Great to see things moving. Could you please do a separate pull for bitfields it should get merged easier and it seems like a small but important bugfix. Guess this means I'll be working on BitArrays a bit later and work instead on the bitfields code. What fun... :) I thought I had bitfields as separate already, but it's kinda thrown both sets of changes in. Once I figure it out I'll get them separated and finish work on the bitfields.
Re: Why must bitfields sum to a multiple of a byte?
On 31-Jul-12 22:21, Era Scarecrow wrote: On Tuesday, 31 July 2012 at 17:17:43 UTC, Timon Gehr wrote: This is obviously a mistake in the bitfield implementation. What else could be concluded from the error message: std\bitmanip.d(76): Error: shift by 32 is outside the range 0..31 Requesting a 32 bit or 64 bit member on the other hand is not a mistake, and it is not useless, therefore the analogy breaks down. Well curiously it was easier to fix than I thought (a line for a static if, and a modification of the masking)... Was there any other bugs that come to mind? Anything of consequence? Great to see things moving. Could you please do a separate pull for bitfields it should get merged easier and it seems like a small but important bugfix. -- Dmitry Olshansky
Re: Why must bitfields sum to a multiple of a byte?
On 07/31/2012 09:15 AM, Era Scarecrow wrote: > On Tuesday, 31 July 2012 at 15:25:55 UTC, Andrej Mitrovic wrote: >> On 7/31/12, monarch_dodra wrote: >>> The bug is only when the field is EXACTLY 32 bits BTW. bitfields >>> works quite nice with 33 or whatever. More details in the report. >> >> Yeah 32 or 64 bits, thanks for changing the title. > > I wonder, is it really a bug? If you are going to have it fill a whole > size it would fit anyways, why even put it in as a bitfield? You could > just declare it separately. It can happen in templated code where the width of the first field may be a template parameter. I wouldn't want to 'static if (width == 32)'. But thanks for fixing the bug already! :) Ali
fixing the bitfields implimentation
On Tuesday, 31 July 2012 at 17:17:43 UTC, Timon Gehr wrote: This is obviously a mistake in the bitfield implementation. What else could be concluded from the error message: std\bitmanip.d(76): Error: shift by 32 is outside the range 0..31 Requesting a 32 bit or 64 bit member on the other hand is not a mistake, and it is not useless, therefore the analogy breaks down. Well curiously it was easier to fix than I thought (a line for a static if, and a modification of the masking)... Was there any other bugs that come to mind? Anything of consequence?
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 17:17:43 UTC, Timon Gehr wrote: This is obviously a mistake in the bitfield implementation. What else could be concluded from the error message: std\bitmanip.d(76): Error: shift by 32 is outside the range 0..31 Requesting a 32 bit or 64 bit member on the other hand is not a mistake, and it is not useless, therefore the analogy breaks down. Well curiously it was easier to fix than I thought (a line for a static if, and a modification of the masking)... Was there any other bugs that come to mind? Anything of consequence?
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 17:34:33 UTC, monarch_dodra wrote:
No, the bug shows itself if the first field is 32 bits,
regardless of (ulong included).
I would add though that requesting a field in bits that is
bigger than the type of the field should not work (IMO). EG:
struct A
{
mixin(bitfields!(
ushort, "a", 24,
uint,"", 8
)
);
}
I don't see any way how that could make sense...
But it *is* legal in C and C++...
But it does generates warnings...
Maybe so ushort has extra padding for expansion at some later
date when they change it to uint?? could put an assert in, but if
it doesn't break code...
I think it should static assert in D.
Glancing over the issue, the [0..31] is a compiler error based
on bit shifting (not bitfields itself); if the storage type is
ulong then it shouldn't matter if the first one is a 32bit size
or not. Unless... Nah, couldn't be... I'll look it over later to
be sure.
That's part of the standard: Statements that have no effect are
illegal. This is a good think, IMO. I've seen MANY C++ bugs
that could have been saved by that.
Regarding the assignment in if. I think it is a good thing. D
sides with safety. If you *really* want to test assign, you can
always comma operator it.
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 17:17:25 UTC, Era Scarecrow wrote:
On Tuesday, 31 July 2012 at 16:59:11 UTC, monarch_dodra wrote:
Maybe the user needs a 32 bit ulong? This way the ulong only
takes 32 bits, but can still be implicitly passed to functions
expecting ulongs.
I would think the bug only showed itself if you did int at
32bits and ulong at 64 bits, not ulong at 32bits.
No, the bug shows itself if the first field is 32 bits,
regardless of (ulong included).
I would add though that requesting a field in bits that is bigger
than the type of the field should not work (IMO). EG:
struct A
{
mixin(bitfields!(
ushort, "a", 24,
uint,"", 8
)
);
}
I don't see any way how that could make sense...
But it *is* legal in C and C++...
But it does generates warnings...
I think it should static assert in D.
On Tuesday, 31 July 2012 at 17:21:00 UTC, Era Scarecrow wrote:
On Tuesday, 31 July 2012 at 17:17:43 UTC, Timon Gehr wrote:
(Also IMO, the once-in-a-year wtf that is caused by
accidentally assigning in an if condition does not justify
special casing assignment expressions inside if conditions.
Also, what is an useless compare?)
I've noticed in my experience, DMD gives you an error if you
do a statement that has no effect; IE:
1 + 2; //statement has no effect
a == b;//ditto
That's part of the standard: Statements that have no effect are
illegal. This is a good think, IMO. I've seen MANY C++ bugs that
could have been saved by that.
Regarding the assignment in if. I think it is a good thing. D
sides with safety. If you *really* want to test assign, you can
always comma operator it.
void main()
{
int a = 0, b = 5;
while(a = --b, a) //YES, I *DO* want to assign!
{
write(a);
}
};
I'm sure the compiler will optimize away what it needs.
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 17:17:43 UTC, Timon Gehr wrote: (Also IMO, the once-in-a-year wtf that is caused by accidentally assigning in an if condition does not justify special casing assignment expressions inside if conditions. Also, what is an useless compare?) I've noticed in my experience, DMD gives you an error if you do a statement that has no effect; IE: 1 + 2; //statement has no effect a == b;//ditto
Re: Why must bitfields sum to a multiple of a byte?
On 07/31/2012 06:57 PM, Era Scarecrow wrote: On Tuesday, 31 July 2012 at 16:48:37 UTC, Andrej Mitrovic wrote: On 7/31/12, Era Scarecrow wrote: I wonder, is it really a bug? If you are going to have it fill a whole size it would fit anyways, why even put it in as a bitfield? You could just declare it separately. I don't really know, I'm looking at this from a point of wrapping C++. I haven't used bitfields myself in my own code. I'd say it's not a bug since C/C++ is free to reorder the fields you'd need to tinker with it anyways; HOWEVER if you still need to be able to have it then who's to stop you from doing it? I think more likely a flag/version or some indicator that you didn't make a mistake, such as making them depreciated so it complains to you. Kinda like how you can't make assignments in if statements or do useless compares, it's an error and helps prevent issues that are quite obviously mistakes. This is obviously a mistake in the bitfield implementation. What else could be concluded from the error message: std\bitmanip.d(76): Error: shift by 32 is outside the range 0..31 Requesting a 32 bit or 64 bit member on the other hand is not a mistake, and it is not useless, therefore the analogy breaks down. (Also IMO, the once-in-a-year wtf that is caused by accidentally assigning in an if condition does not justify special casing assignment expressions inside if conditions. Also, what is an useless compare?)
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 16:59:11 UTC, monarch_dodra wrote: No, it's a bug. There is no reason for it to fail (and it certainly isn't a feature). If I made two fields in a 64bit bitfield, each 32bits int's I'd like it to complain; If it's calculated from something else then finding the problem may be a little more difficult. But that's how my mind works, give you the tools you need to do whatever you want including shooting yourself in the foot (although you need to work harder to do that than C++). Maybe the user wants to pack an "uint, ushort, ubyte, ubyte" together in a struct, but doesn't want the rest of that struct's members 1-aligned? That would be the one reason that makes sense; Course can't you align sections at 1 byte and then by the default afterwards? Course now that I think about it, some systems don't have options to do byte alignments and require to access memory at 4/8 byte alignments. This makes sense needing to support it. Maybe the user needs a 32 bit ulong? This way the ulong only takes 32 bits, but can still be implicitly passed to functions expecting ulongs. I would think the bug only showed itself if you did int at 32bits and ulong at 64 bits, not ulong at 32bits. Maybe the user generated the mixin using another template? For example, testing integers from 10 bits wide to 40 bits wide? Should he write a special case for 32? Ummm. Yeah I think I see what your saying; And you're probably right a special case would be less easily documented (and more a pain) when it shouldn't need a special case. Now I'm not saying it is big bug or anything, but it is something that should be supported... Or at least explicitly asserted until fixed...
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 16:16:00 UTC, Era Scarecrow wrote: On Tuesday, 31 July 2012 at 15:25:55 UTC, Andrej Mitrovic wrote: On 7/31/12, monarch_dodra wrote: The bug is only when the field is EXACTLY 32 bits BTW. bitfields works quite nice with 33 or whatever. More details in the report. Yeah 32 or 64 bits, thanks for changing the title. I wonder, is it really a bug? If you are going to have it fill a whole size it would fit anyways, why even put it in as a bitfield? You could just declare it separately. I get the feeling it's not so much a bug as a design feature. If you really needed a full size not aligned with whole bytes (or padded appropriately) then I could understand, but still... And I'm the one that changed the title name. Suddenly I'm reminded of south park (movie) and the buttfor. No, it's a bug. There is no reason for it to fail (and it certainly isn't a feature). Maybe the user wants to pack an "uint, ushort, ubyte, ubyte" together in a struct, but doesn't want the rest of that struct's members 1-aligned? Maybe the user needs a 32 bit ulong? This way the ulong only takes 32 bits, but can still be implicitly passed to functions expecting ulongs. Maybe the user generated the mixin using another template? For example, testing integers from 10 bits wide to 40 bits wide? Should he write a special case for 32? ... Now I'm not saying it is big bug or anything, but it is something that should be supported... Or at least explicitly asserted until fixed...
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 16:48:37 UTC, Andrej Mitrovic wrote: On 7/31/12, Era Scarecrow wrote: I wonder, is it really a bug? If you are going to have it fill a whole size it would fit anyways, why even put it in as a bitfield? You could just declare it separately. I don't really know, I'm looking at this from a point of wrapping C++. I haven't used bitfields myself in my own code. I'd say it's not a bug since C/C++ is free to reorder the fields you'd need to tinker with it anyways; HOWEVER if you still need to be able to have it then who's to stop you from doing it? I think more likely a flag/version or some indicator that you didn't make a mistake, such as making them depreciated so it complains to you. Kinda like how you can't make assignments in if statements or do useless compares, it's an error and helps prevent issues that are quite obviously mistakes.
Re: Why must bitfields sum to a multiple of a byte?
On 7/31/12, Era Scarecrow wrote: > I wonder, is it really a bug? If you are going to have it fill a > whole size it would fit anyways, why even put it in as a > bitfield? You could just declare it separately. I don't really know, I'm looking at this from a point of wrapping C++. I haven't used bitfields myself in my own code.
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 15:25:55 UTC, Andrej Mitrovic wrote: On 7/31/12, monarch_dodra wrote: The bug is only when the field is EXACTLY 32 bits BTW. bitfields works quite nice with 33 or whatever. More details in the report. Yeah 32 or 64 bits, thanks for changing the title. I wonder, is it really a bug? If you are going to have it fill a whole size it would fit anyways, why even put it in as a bitfield? You could just declare it separately. I get the feeling it's not so much a bug as a design feature. If you really needed a full size not aligned with whole bytes (or padded appropriately) then I could understand, but still... And I'm the one that changed the title name. Suddenly I'm reminded of south park (movie) and the buttfor.
Re: Why must bitfields sum to a multiple of a byte?
On 7/31/12, monarch_dodra wrote: > The bug is only when the field is EXACTLY 32 bits BTW. bitfields > works quite nice with 33 or whatever. More details in the report. Yeah 32 or 64 bits, thanks for changing the title.
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 00:44:16 UTC, Andrej Mitrovic wrote: On 7/31/12, Era Scarecrow wrote: It assumes the largest type we can currently use which is ulong Ah yes, it makes sense now. Thanks for the brain cereal. :p I saw your bug report: http://d.puremagic.com/issues/show_bug.cgi?id=8474 The bug is only when the field is EXACTLY 32 bits BTW. bitfields works quite nice with 33 or whatever. More details in the report.
Re: BitArray/BitFields - Review
On 29/07/12 23:36, bearophile wrote: Era Scarecrow: >>> Another commonly needed operation is a very fast bit count. There are very refined algorithms to do this. Likely similar to the hamming weight table mentioned in TDPL. Combined with the canUseBulk I think I could make it fairly fast. There is lot of literature about implementing this operation efficiently. For the first implementation a moderately fast (and short) code is probably enough. Later faster versions of this operation will go in Phobos, coming from papers. See bug 4717. On x86, even on 32 bits you can get close to 1 cycle per byte, on 64 bits you can do much better.
Re: BitArray/BitFields - Reworking with templates
On Tuesday, 31 July 2012 at 05:27:58 UTC, Philippe Sigaud wrote:
No. Use a 3-params template or a tuple:
void func(A,B,C)(X!(A,B,C) x) {}
or
void func(Ts...)(X!(Ts) x) {}
I don't know how many arguments it will have (depends on how
many options I give it), and I honestly don't; It should be
invisible for the end user as long as we can get the the
constraints properly accepted.
or even, more general:
void func(T)(T x) if (is(T t = X!(SomeTypes), SomeTypes...)),
because template constrains are much more powerful and general
than fiddling arguments types.
That doesn't make sense; but I don't have a full grasp of the
templates (continued below).
There was a discussion between Simen Kjaeraas and me on the
subject not long ago. Kenji Hara extended the functionnality of
is( , T...) and did a pull request. I'm not sure it's in 2.060,
the request was done a week ago.
so the (, T...) is shorthand for testing the template type with
multiple arguments. Nice. So multiple arguments would be...
struct X (T, U) {}
if(is(T t = X!(bool, bool), (int, int), (int, bool))) //?
I want to say no... But I haven't actually tested it for my
use cases. Leaving it unconstrained (without checking) to make
it work is a disaster waiting to happen: I want T and U to
both be of the same template (X in this case) but not the same
instantiation arguments.
Said like this, it's much more clear for me :)
Note that in the above code, SomeType is a fresh variable in
each is() expression. So, even though I used the same name
(shouldn't have done that), T and U can have different type
parameters.
*shameless plug*
Btw, I wrote a tutorial on templates, you can find it here:
https://github.com/PhilippeSigaud/D-templates-tutorial/blob/master/dtemplates.pdf
(click on 'view raw', that should download the pdf)
That should shed some light on the matters at hand.
Indeed... I remember glancing through it, but never really
needed it badly; Now it seems I do. At least it's not C++ and
it's templates. I'll be reading up on them starting tonight (and
printing most of it); It is after all the hardest part (and most
powerful part) of the language :P
Re: BitArray/BitFields - Reworking with templates
On Mon, Jul 30, 2012 at 11:19 PM, Era Scarecrow wrote:
>> void func(T)(X!T x)
>> {}
>>
>> void main()
>> {
>> X!bool b;
>> X!int i;
>> func(b);
>> func(i);
>> }
>
>
> Hmmm i do think that seems right... but if it contains multiple parameters,
> then...?
>
> template X(x1, x2, x3) {
> struct XT {}
> }
>
>> void func(T)(X!T x) {}
>
> Will this still work?
No. Use a 3-params template or a tuple:
void func(A,B,C)(X!(A,B,C) x) {}
or
void func(Ts...)(X!(Ts) x) {}
or even, more general:
void func(T)(T x) if (is(T t = X!(SomeTypes), SomeTypes...)), because
template constrains are much more powerful and general than fiddling
arguments types.
There was a discussion between Simen Kjaeraas and me on the subject
not long ago. Kenji Hara extended the functionnality of is( , T...)
and did a pull request. I'm not sure it's in 2.060, the request was
done a week ago.
>> void tempFunc(T,U)(T t, U u) if (is(T a == X!(SomeType), SomeType) &&
>> is(U a == X!(SomeType), SomeType)
>> || is(T == XY) && is(U ==
>> XY))
>> {
>> ...
>> }
>> Is that what you need?
>
>
> I want to say no... But I haven't actually tested it for my use cases.
> Leaving it unconstrained (without checking) to make it work is a disaster
> waiting to happen: I want T and U to both be of the same template (X in this
> case) but not the same instantiation arguments.
Said like this, it's much more clear for me :)
Note that in the above code, SomeType is a fresh variable in each is()
expression. So, even though I used the same name (shouldn't have done
that), T and U can have different type parameters.
*shameless plug*
Btw, I wrote a tutorial on templates, you can find it here:
https://github.com/PhilippeSigaud/D-templates-tutorial/blob/master/dtemplates.pdf
(click on 'view raw', that should download the pdf)
That should shed some light on the matters at hand.
Re: Why must bitfields sum to a multiple of a byte?
On 7/31/12, Era Scarecrow wrote: > It assumes the largest type we can currently use which is ulong Ah yes, it makes sense now. Thanks for the brain cereal. :p
Re: Why must bitfields sum to a multiple of a byte?
On Tuesday, 31 July 2012 at 00:00:24 UTC, Era Scarecrow wrote:
Corrections:
So, 2 variables using 4 bit ints would be
void a(int v) @property {
value &= ~(0x7 << 4);
value |= (v & 0x7) << 4;
}
the second setter should be
void b(int v) @property {
Re: Why must bitfields sum to a multiple of a byte?
On Monday, 30 July 2012 at 23:41:39 UTC, Andrej Mitrovic wrote:
On 7/31/12, Era Scarecrow wrote:
And likely one I'll be working on fairly soon. I've been
concentrating on the BitArray, but I'll get more of the
bitfields very very soon.
Cool. What about the Max limit of 64bits per bitfield
instantiation? I don't suppose this is common in C++ but I
wouldn't know..
The limitation is based on what kind of types you can use. If
you want a field 1000 bits long, i don't see why not; But
obviously you can't treat it like an int or bool. (No cheap way
to make a BigInt here :P), and packing say a struct, it would be
slow since it has to copy each bit individually, or if it's byte
aligned, by bytes.
It assumes the largest type we can currently use which is ulong,
if cent ever gets properly added, then 128bits will become
available. If they want to go higher than likely type 'dime' or
'nickel' or bicent (256bits? :P) can be used once the template is
modified. Maybe tricent can be 384 and quadcent can be 512
Mmmm :) or it could just be large256, ularge256.
As for the 'why', is that all of the bitfields work by assuming
bit-shifting and low level binary operators to do the job. So, 2
for 4 ints would be
int value;
int a() @property {
return value & 0x7;
}
void a(int v) @property {
value &= ~0x7;
value |= v & 0x7;
}
int b() @property {
return (value>>4) & 0x7;
}
void a(int v) @property {
value &= ~(0x7 << 4);
value |= (v & 0x7) << 4;
}
That may be flawed but it gives you a basic idea.
Re: Why must bitfields sum to a multiple of a byte?
On 7/31/12, Era Scarecrow wrote: > And likely one I'll be working on fairly soon. I've been > concentrating on the BitArray, but I'll get more of the bitfields > very very soon. > Cool. What about the max limit of 64bits per bitfield instantiation? I don't suppose this is common in C++ but I wouldn't know..
Re: Why must bitfields sum to a multiple of a byte?
On Monday, 30 July 2012 at 17:43:28 UTC, Ali Çehreli wrote:
On 07/30/2012 10:15 AM, Andrej Mitrovic wrote:
> import std.bitmanip;
> struct Foo
> {
> mixin(bitfields!(
> uint, "bits1", 32,
> ));
> }
>
> D:\DMD\dmd2\windows\bin\..\..\src\phobos\std\bitmanip.d(76):
Error:
> shift by 32 is outside the range 0..31
>
> Should I file this?
Yes, it's a bug.
And likely one I'll be working on fairly soon. I've been
concentrating on the BitArray, but I'll get more of the bitfields
very very soon.
Re: BitArray/BitFields - Reworking with templates
On Monday, 30 July 2012 at 22:44:21 UTC, Dmitry Olshansky wrote:
Fixed :
void func(bool smth)(X!(smth).XT x){
By default XT is deduced as X!(current value of smth).XT
Doesn't really fix it...
a.func(b); //65 - doesn't match declaration.
a.func(ba); //66
//other template tests not worth putting, 67-70
a.func!true(b); //71 - explicitly stated
a.func!false(ba); //72
a.func!false(b); //73 - Backwards on purpose for test
a.func!true(ba); //74
(65): Error: template test.X!(true).XT.func does not match any
function template declaration
(11): Error: template test.X!(true).XT.func(bool smth) cannot
deduce template function from argument types !()(XT)
(66): Error: template test.X!(true).XT.func does not match any
function template declaration
(11): Error: template test.X!(true).XT.func(bool smth) cannot
deduce template function from argument types !()(XT)
(73): Error: function test.X!(true).XT.func!(false).func (XT x)
is not callable using argument types (XT)
(73): Error: cannot implicitly convert expression (b) of type XT
to XT
(74): Error: function test.X!(true).XT.func!(true).func (XT x) is
not callable using argument types (XT)
(74): Error: cannot implicitly convert expression (ba) of type XT
to XT
Re: BitArray/BitFields - Reworking with templates
On 31-Jul-12 02:40, Era Scarecrow wrote:
On Monday, 30 July 2012 at 22:23:46 UTC, Era Scarecrow wrote:
On Monday, 30 July 2012 at 21:56:20 UTC, Dmitry Olshansky wrote:
in == scope const not sure what scope buys here but couldn't hurt.
If it can avoid making a new copy, then it likely would help. I'll
need to test it. I actually am not quite sure how scope works as an
argument; it isn't really covered in TDPL from what I recall.
Tests with 'in' doesn't help, only ref and catching a temporary seem
to prevent postblits.
Also the empty template doesn't work, somehow I'm not surprised...
template X(bool something) {
struct XT {
Fixed :
void func(bool smth)(X!(smth).XT x){
By default XT is deduced as X!(current value of smth).XT
writeln("XT template called: typeID:", typeid(x));
}
}
}
alias X!true.XT A;
alias X!false.XT B;
A a, b;
B ba;
a.func(b); //passes
a.func(ba);
Error: template test.X!(true).XT.func does not match any function
template declaration
Error: template test.X!(true).XT.func() cannot deduce template function
from argument types !()(XT)
--
Dmitry Olshansky
Re: BitArray/BitFields - Reworking with templates
On Monday, 30 July 2012 at 22:23:46 UTC, Era Scarecrow wrote:
On Monday, 30 July 2012 at 21:56:20 UTC, Dmitry Olshansky wrote:
in == scope const not sure what scope buys here but couldn't
hurt.
If it can avoid making a new copy, then it likely would help.
I'll need to test it. I actually am not quite sure how scope
works as an argument; it isn't really covered in TDPL from what
I recall.
Tests with 'in' doesn't help, only ref and catching a temporary
seem to prevent postblits.
Also the empty template doesn't work, somehow I'm not surprised...
template X(bool something) {
struct XT {
void func()(XT x){
writeln("XT template called: typeID:", typeid(x));
}
}
}
alias X!true.XT A;
alias X!false.XT B;
A a, b;
B ba;
a.func(b); //passes
a.func(ba);
Error: template test.X!(true).XT.func does not match any function
template declaration
Error: template test.X!(true).XT.func() cannot deduce template
function from argument types !()(XT)
Re: BitArray/BitFields - Reworking with templates
On Monday, 30 July 2012 at 21:56:20 UTC, Dmitry Olshansky wrote:
You can go for simpler separation:
struct BitArray{
//() - is an empty template spec
ref BitArrayopSliceAssign()(const BitArray ba, int start, int
end)
{
//two bit array can try balk mode etc.
I'll give it a try, it may very well be what I need; although I
wouldn't have thought you could declare it like that. I have much
to learn in the ways of the template.
course if the 'in' keyword is the key i will have to test
that to make sure.
in == scope const not sure what scope buys here but couldn't
hurt.
If it can avoid making a new copy, then it likely would help.
I'll need to test it. I actually am not quite sure how scope
works as an argument; it isn't really covered in TDPL from what I
recall.
Re: BitArray/BitFields - Reworking with templates
On 31-Jul-12 01:03, Era Scarecrow wrote:
On Monday, 30 July 2012 at 20:19:51 UTC, Dmitry Olshansky wrote:
Not sure what you would like to accomplish here.
Than an example...
You can go for simpler separation:
struct BitArray{
//() - is an empty template spec
ref BitArrayopSliceAssign()(const BitArray ba, int start, int end)
{
//two bit array can try balk mode etc.
Reminds me. Due to how rvalue/lvalues work, assuming I need to const
reference something but I don't care if it's a temporary or not, would I
then do...
struct X {
int opCmp(const X x) const { //catch temporary
return opCmp(x); //becomes reference, as it's now named 'x'
}
int opCmp(const ref X x) const {
//do work here
return 0;
}
}
X x;
assert(x == x); //ref
assert(x == X()); //temporary
course if the 'in' keyword is the key i will have to test that to make
sure.
in == scope const not sure what scope buys here but couldn't hurt.
--
Dmitry Olshansky
Re: BitArray/BitFields - Reworking with templates
On Monday, 30 July 2012 at 20:48:26 UTC, Philippe Sigaud wrote:
Now if all that is correct, say I want to make two functions
that both use X, but are not compatible, but template
functions will allow it. So...
I'm not sure I understand what you're trying to do. Do you mean
you want a function that accept X!(T)s for any T, and not any
other type?
Anything of template X! previous post of mine shows sort of an
example.
struct X(T) {}
void func(T)(X!T x)
{}
void main()
{
X!bool b;
X!int i;
func(b);
func(i);
}
Hmmm i do think that seems right... but if it contains multiple
parameters, then...?
template X(x1, x2, x3) {
struct XT {}
}
void func(T)(X!T x) {}
Will this still work?
Here you want a constraint that checks that U and T are both
X!(SomeType) or an XY?
As before, of Template X, and struct XY, but T (or sometype)
doesn't matter.
void tempFunc(T,U)(T t, U u) if (is(T a == X!(SomeType),
SomeType) &&
is(U a == X!(SomeType), SomeType)
|| is(T == XY)
&& is(U == XY))
{
...
}
Is that what you need?
I want to say no... But I haven't actually tested it for my use
cases. Leaving it unconstrained (without checking) to make it
work is a disaster waiting to happen: I want T and U to both be
of the same template (X in this case) but not the same
instantiation arguments.
I hope I'm not repeating myself too much.
Re: BitArray/BitFields - Reworking with templates
On Monday, 30 July 2012 at 21:03:39 UTC, Era Scarecrow wrote: Alright... Considered a major (Maybe even blocking). http://d.puremagic.com/issues/show_bug.cgi?id=8475
Re: BitArray/BitFields - Reworking with templates
On Monday, 30 July 2012 at 20:19:51 UTC, Dmitry Olshansky wrote:
Not sure what you would like to accomplish here.
Than an example...
struct BitArray { //assume template...
ref BitArray opSliceAssign(T)(const T ba, int start, int end)
if (
//if T is type bitArray but only a different change regarding
parameters
//we can use canUseBulk and other speedups. Otherwise a range
is required.
//checking all possibilities seems silly, but possible
)
body {
//slice specific speedup and code
return this;
}
int opEquals(T)(const T ba) const
//if constraint as above
body {}
}
Code wise; If BitSet is always value semantics and BitArray is
always reference (a previous post) and slices/groups work
basically the same; then...
BitSet bs = BitSet(100);
BitArray ba = BitArray(100);
bs[0 .. 10] = ba[0 .. 10]; //should work
assert(bs[0 .. 10] == ba[0 .. 10]); //should also be possible to
work.
alias X!(true).XY Xtrue;
pure function 'func' cannot call impure function '__cpctor'
safe function 'func' cannot call system function '__cpctor'
Yeah, it's a bug. File it please.
Alright... Considered a major (Maybe even blocking).
Reminds me. Due to how rvalue/lvalues work, assuming I need to
const reference something but I don't care if it's a temporary or
not, would I then do...
struct X {
int opCmp(const X x) const { //catch temporary
return opCmp(x); //becomes reference, as it's now named 'x'
}
int opCmp(const ref X x) const {
//do work here
return 0;
}
}
X x;
assert(x == x); //ref
assert(x == X()); //temporary
course if the 'in' keyword is the key i will have to test that
to make sure.
Re: BitArray/BitFields - Reworking with templates
On Mon, Jul 30, 2012 at 9:50 PM, Era Scarecrow wrote:
> A question regarding templates. A template with different parameters is
> completely incompatible correct?
Correct. They have no reason, in general, too even generate the same code:
template Chameleon(T)
{
static if (is(T == struct))
enum Chameleon = "I'm a string!"; // Chamelon!(SomeStruct) is
a string value
else static if (is(T == class))
void Chameleon(int i) { return i+1;} // Chameleon!(SomeClass)
is a function
else
alias T[int] Chameleon; // Here Chameleon is a type
}
The same for you struct S(T) { ... }. Inside the braces, anything can
happen (mwwaahhha hhaa!), depending on T.
> So...
>
> struct X(T) {
> }
>
> alias X!bool XB;
> alias X!int XI;
>
> void func(XB xb) {
>
> }
>
> func(XB()); //works
> func(XI()); //should fail to compile
Yes.
> Now if all that is correct, say I want to make two functions that both use
> X, but are not compatible, but template functions will allow it. So...
I'm not sure I understand what you're trying to do. Do you mean you
want a function that accept X!(T)s for any T, and not any other type?
struct X(T) {}
void func(T)(X!T x)
{}
void main()
{
X!bool b;
X!int i;
func(b);
func(i);
}
> void tempFunc(T, U)(T t, U u)
> if(
> //What do i enter to check they are both template X or struct XY? As
> signatures will be different...
> )
> body{
> //now acts as a middle-man to be compatible for said operation
> }
Here you want a constraint that checks that U and T are both
X!(SomeType) or an XY?
void tempFunc(T,U)(T t, U u) if (is(T a == X!(SomeType), SomeType) &&
is(U a == X!(SomeType), SomeType)
|| is(T == XY) && is(U == XY))
{
...
}
Is that what you need?
Re: BitArray/BitFields - Reworking with templates
On 30-Jul-12 23:50, Era Scarecrow wrote:
On Sunday, 29 July 2012 at 12:39:13 UTC, Era Scarecrow wrote:
But having them statically separated by name/type seems much more
likely to be safer in the long run with reliable results.
A question regarding templates. A template with different parameters
is completely incompatible correct? So...
Yeah, like twin brothers the have different IDs :)
struct X(T) {
}
alias X!bool XB;
alias X!int XI;
void func(XB xb) {
}
func(XB()); //works
func(XI()); //should fail to compile
Same if it was built differently? so...
template X(bool something) //'bool something' should be statically
checkable
struct XY {
static if (something) {
//conditional functions or code
}
XY makeX(){
//XY type is only currently formed template version correct?
return XY();
}
}
}
//against above func, with these two...
alias X!(false).XY XB;
alias X!(true).XY XI;
Course if there's a way to avoid asking about the inner XY, I wonder how
I would do that.
Now if all that is correct, say I want to make two functions that both
use X, but are not compatible, but template functions will allow it. So...
void tempFunc(T, U)(T t, U u)
if(
//What do i enter to check they are both template X or struct XY? As
signatures will be different...
)
body{
//now acts as a middle-man to be compatible for said operation
}
Not sure what you would like to accomplish here.
alias X!(true).XY Xtrue;
pure function 'func' cannot call impure function '__cpctor'
safe function 'func' cannot call system function '__cpctor'
Yeah, it's a bug. File it please.
--
Dmitry Olshansky
BitArray/BitFields - Reworking with templates
On Sunday, 29 July 2012 at 12:39:13 UTC, Era Scarecrow wrote:
But having them statically separated by name/type seems much
more likely to be safer in the long run with reliable results.
A question regarding templates. A template with different
parameters is completely incompatible correct? So...
struct X(T) {
}
alias X!bool XB;
alias X!int XI;
void func(XB xb) {
}
func(XB()); //works
func(XI()); //should fail to compile
Same if it was built differently? so...
template X(bool something) //'bool something' should be
statically checkable
struct XY {
static if (something) {
//conditional functions or code
}
XY makeX(){
//XY type is only currently formed template version correct?
return XY();
}
}
}
//against above func, with these two...
alias X!(false).XY XB;
alias X!(true).XY XI;
Course if there's a way to avoid asking about the inner XY, I
wonder how I would do that.
Now if all that is correct, say I want to make two functions
that both use X, but are not compatible, but template functions
will allow it. So...
void tempFunc(T, U)(T t, U u)
if(
//What do i enter to check they are both template X or struct
XY? As signatures will be different...
)
body{
//now acts as a middle-man to be compatible for said operation
}
Finally, I came across an anomaly and may just be a bug. What
about a postblits?
T func2(T)(T x) @safe pure {
return T();
}
struct XY {
this(this) @safe pure {} //safe pure added so func can call it
void func(XY x) @safe pure {
XY y = x; //postblits called on all three lines
func2(x);
func2(y);
}
}
template X(bool something) {
struct XY {
this(this) @safe pure {}
void func(XY x) @safe pure {
XY y = x; //Error: see below
func2(x);
func2(y);
}
}
}
alias X!(true).XY Xtrue;
pure function 'func' cannot call impure function '__cpctor'
safe function 'func' cannot call system function '__cpctor'
Re: BitArray/BitFields - Review
Era Scarecrow: If it has to determine between compact and non-compact, then I really don't see how any speed improvement can be made, Maybe it's better to consider two use cases: dynamic length allocated on the heap (or allocated with a given allocator, often a stack-styled allocator), and fixed-size allocated in place, so there's no need for that run-time test. and if it's optimized it may be inlined which would be about as fast as you could get. I think that "a[x] = 1;" is slower than "a.set(x);" even if the array a is allocated in place and everything is inlined. This is probably the most important operation an array of bits has to support. If this is missing, I have to use my own implementation still. Likely similar to the hamming weight table mentioned in TDPL. Combined with the canUseBulk I think I could make it fairly fast. There is lot of literature about implementing this operation efficiently. For the first implementation a moderately fast (and short) code is probably enough. Later faster versions of this operation will go in Phobos, coming from papers. Yes, currently a debate of it's partial ref/value issue is coming up. As it is it's usable, and if you want to be sure it's unique you can always dup it, otherwise as a previous suggestion I'll either make two array types for either full reference vs value, or take his separate slices (reference) idea. The idea of making two different types (for the dynamic and static versions) sounds nice. There is a third use case, that is bit arrays that start small and can grow, and rarely grow bigger than one or two words. This asks for a dynamic-length bit array type that allocates locally only when it's small (so it needs to perform run-time test of the tag. Too bad the D GC doesn't support tagged pointers!). But probably this use case is not common enough to require a third type of array. So I suggest to not worry about this case now, and to focus on the other two more common ones. A Matrix is just a multidimensional array right? Well, yes, but there are many ways to implement arrays and nD arrays. Sometimes the implementations differ. I'll have to read up on it a bit; doing simple division (Likely whole rows of 32bit at a time) would do that job, Take a look at my implementation in Bugzilla :-) It's another type, the third. The 1D and 2D cases are the most common. but expanding width several times (compared to height) would be quite a bit slower; Although not too horrible. A 2D array of bits probably doesn't need to change its size after creation, this is not a common use case. more likely bool array/matrix.. Although if you heavily use specific lines it could convert to bool[], and then back again, but if you go all over the place it would be worse than just using bool[]. It's not so simple :-) A bool[] causes many more cache misses, if the matrix is not tiny. A bool[] or bool[][] is a good idea only if the matrix is very small, or if you don't have a bit matrix library and you don't want to write lot of code. Converting to bool[] the current line is not a good idea. Bye, bearophile
Re: BitArray/BitFields - Review
On Sunday, 29 July 2012 at 14:41:48 UTC, bearophile wrote: As you guess I have had to use many arrays of bits in my programs :-) I'll do what I can :) 4124 - Set/reset all bits ie: BitArray ba = BitArray(100); ba[] = true; Others haven't been done yet. Among those 4124 suggestions the most important, and very simple to implement, are: - set n-th bit (this can be a little more efficient than bs[n]=1;) - reset n-th bit (this can be a little more efficient than bs[n]=1;) If it has to determine between compact and non-compact, then I really don't see how any speed improvement can be made, and if it's optimized it may be inlined which would be about as fast as you could get. Another commonly needed operation is a very fast bit count. There are very refined algorithms to do this. Likely similar to the hamming weight table mentioned in TDPL. Combined with the canUseBulk I think I could make it fairly fast. 7487 - Done. When prepending it extends the array to size_t extra and slowly backtracks until it needs to do it again. Leaving a bit of "capacity" at the beginning is a good idea. With how it's made for speed and slices, it had to :P 7488 - Done, union used and is 'compact' version (by default or resized and can fit) Good, this makes BitArray usable in many other situations :-) Yes, currently a debate of it's partial ref/value issue is coming up. As it is it's usable, and if you want to be sure it's unique you can always dup it, otherwise as a previous suggestion I'll either make two array types for either full reference vs value, or take his separate slices (reference) idea. Related: http://d.puremagic.com/issues/show_bug.cgi?id=6697 Not so sure. Could make a multi-dimentional one that returns slices to various sections, but that's iffy. I'd need an example of how you'd use it with BitArray before I could build a solution. I have needed many times a fast BitMatrix, but I see it as a data structure distinct from BitArray, so don't worry about making them inter-operate. A Matrix is just a multidimensional array right? I'll have to read up on it a bit; doing simple division (Likely whole rows of 32bit at a time) would do that job, but expanding width several times (compared to height) would be quite a bit slower; Although not too horrible. For me a BitMatrix must be as fast as possible, even if this causes some waste of memory (see my implementation in the attach of issue 6697) and I use it for medium and large bit matrices. Generally I don't to count the set bits in a bit matrix. So the two data structures need different capabilities and they are better implemented in different ways (this means a FastBitMatrix is not an array of a BitArray!). more likely bool array/matrix.. Although if you heavily use specific lines it could convert to bool[], and then back again, but if you go all over the place it would be worse than just using bool[]. Taking a row of a FastBitMatrix and turning it into a a BitArray sounds cute, but generally I don't need to do this operation, so I don't care about this feature.
Re: BitArray/BitFields - Review
Era Scarecrow: As you guess I have had to use many arrays of bits in my programs :-) 4124 - Set/reset all bits ie: BitArray ba = BitArray(100); ba[] = true; Others haven't been done yet. Among those 4124 suggestions the most important, and very simple to implement, are: - set n-th bit (this can be a little more efficient than bs[n]=1;) - reset n-th bit (this can be a little more efficient than bs[n]=1;) Another commonly needed operation is a very fast bit count. There are very refined algorithms to do this. 7487 - Done. When prepending it extends the array to size_t extra and slowly backtracks until it needs to do it again. Leaving a bit of "capacity" at the beginning is a good idea. 7488 - Done, union used and is 'compact' version (by default or resized and can fit) Good, this makes BitArray usable in many other situations :-) Related: http://d.puremagic.com/issues/show_bug.cgi?id=6697 Not so sure. Could make a multi-dimentional one that returns slices to various sections, but that's iffy. I'd need an example of how you'd use it with BitArray before I could build a solution. I have needed many times a fast BitMatrix, but I see it as a data structure distinct from BitArray, so don't worry about making them inter-operate. For me a BitMatrix must be as fast as possible, even if this causes some waste of memory (see my implementation in the attach of issue 6697) and I use it for medium and large bit matrices. Generally I don't to count the set bits in a bit matrix. So the two data structures need different capabilities and they are better implemented in different ways (this means a FastBitMatrix is not an array of a BitArray!). Taking a row of a FastBitMatrix and turning it into a a BitArray sounds cute, but generally I don't need to do this operation, so I don't care about this feature. Bye, bearophile
Re: BitArray/BitFields - Review
On Sunday, 29 July 2012 at 09:30:06 UTC, Dmitry Olshansky wrote: I have simpler suggestion. Maybe doing it as 2 containers: BitSet is a plain value type with small array optimization (what you called BitArray in last 2 posts) and no slicing (only as opSlice() I.e. as a whole). Best used for small things under < 1000 bits (as even dup will be cheap enough). BitArray is class or struct that has reference semantics and drops small array optimization in favor of having simple & fast slicing Best used for big arrays with no less then 100-200 bits. Another thought coming to mind, is to have the BitArray with a few different modes it could operate in. One of the modes could be 'reference' which would make slices and them all work exactly as you would expect, while with referencing off it would act as a normal value type struct, since the mode/flags would modify how the postblit and assignment operators worked, along with the length. (Reference wouldn't use small array optimization). But having them statically separated by name/type seems much more likely to be safer in the long run with reliable results.
