Subject: getting the "address" of a bitfield / rewriting style switches

From: Dominik Vogt <[email-masked]>
Date: Fri, 2 Aug 2002 10:37:33 +0200

I'd like to rewrite the style code that handles simple switches.
At the moment, we have a big chain of "if () ... else if () ..."
statements which is ugly, inefficient and requires a lot of
maintenance when things change.

What I'm aiming at is to put all the simple style switches that
just toggle a single bit in a big, sorted list.  The "Style"
command would use bsearch to find the given style in that list
and set or delete the corresponding bits.  For example, the
current code

  ...
  else if (StrEquals(token, "Sticky"))
  {
    found = True;
    SFSET_IS_STICKY(*ptmpstyle, 1);
    SMSET_IS_STICKY(*ptmpstyle, 1);
    SCSET_IS_STICKY(*ptmpstyle, 1);
  }
  else if (StrEquals(token, "Slippery"))
  {
    found = True;
    SFSET_IS_STICKY(*ptmpstyle, 0);
    SMSET_IS_STICKY(*ptmpstyle, 1);
    SCSET_IS_STICKY(*ptmpstyle, 1);
  }
  ...

would become

  /* type declarations */
  typedef struct
  {
     size_t byte_offset_from_start;
     unsigned char bit_mask_in_byte;
  } bit_address_t
  typedef struct
  {
    char *switch_name;
    bit_address_t flag_address;
    unsigned flag_value : 1;
  } style_switch_entry_t;
  typedef style_switch_entry_t *style_switch_table_t;

  /* the style switch table */
  static style_switch_table_t style_switch_table[] =
  {
    ...
    { "Slippery", {<address of is_sticky bit in common_flags_type>}, 0 },
    ...
    { "Sticky",   {<address of is_sticky bit in common_flags_type>}, 1 },
    ...
  }

Only the few more complex styles need the "if...else if..." chain.

The problem:  given an address of a flags structure:

  common_flags_type *flags;

and the name of a member, e.g. "is_sticky" or "s.is_size_fixed".
How do we get the offset of the byte that holds the flag in the
structure and the bit number in that byte?  A solution that works
at compile time is preferred, but it wouldn't be too bad to fill
the table at run time.  The solution must work on any hardware,
regardless of the byte, word or dword order.

One idea for a compile time solution:

Write a small program that creates a structure "flags" of the
given type and zeros it.  Then it sets the given flag with

  flags.<flag_name> = 1;

Finally, it searches for the byte that now has a bit set to 1,
takes its offset from the start of the structure as
byte_offset_from_start and its value as bit_mask_in_byte and
generates a table entry in a file that implements the style switch
list.

But this solution is ugly and complicates the build process.  I'm
not very fond of files that are generated at build time.  Instead,
it would be better to have some macros or whatever that do the
calculations at preprocessing time without the help of external
programs.

Ideas, please!

Long term goal:  Allow *all* style switch names in conditional
commands without duplicating the code to parse their names, e.g.

  next (Style GrabFocus, Style NoBorder) foobar

Bye

Dominik ^_^  ^_^

 --
Dominik Vogt, mail: [email-masked], phone: 0721/91374-382
Schlund + Partner AG, Erbprinzenstr. 4-12, D-76133 Karlsruhe
--
Visit the official FVWM web page at <URL:http://www.fvwm.org/>.
To unsubscribe from the list, send "unsubscribe fvwm-workers" in the
body of a message to [email-masked].
To report problems, send mail to [email-masked]

---

From: Dave Trollope <[email-masked]>
Date: Sat, 03 Aug 2002 22:53:21 -0500

Hi Dominik

After pondering over this for several hours, I have some questions that I
hope will drive the ultimate solution, whatever that maybe. Forgive my
verbosity.

The impression I get is that you want to retain the existing code that reads
the flags without change. I see this as beneficial simply from a performance
stand point. I don't see a solution without generating code at compile time.
As you say generating code would complicate the build process and I think
there are other simpler solutions if the code that access' the data is also
modified. I don't think that should be a big deal in this scenario because
there are existing macros which access the data, so the change can be
relatively hidden.

The fundamental problem here is the bitfield specification since C doesn't
handle that well. Perhaps instead of using bitfields a char would suffice but
it would be a waste. Approximately how many options are we talking in this
code, a hundred?

Before I go on rambling about solutions, pros and cons, I would like to
discuss one observation. In the long if else if chain, it seems that for each
flag, three internal flags are set. Since I am not familar with this code
there may be very good reason for this, however I propose that part of the
solution changes this such that only one field is written with all three
flags at once. To write three separate memory locations at once all the time
is inefficient. Do you agree that it would be better to store all three flags
together instead of separately? This would also lessen the need for bitfield
use but would still leave a large number of unused bits per byte.

OK, so moving forward assuming that the get and set macros are to be
rewritten, and all access to the data go through the macros, I think I would
simply define a char array, assign a bit position for each flag within each
entry, and statically define the index for each option.

#define MERGE_OPTS(_f,_c,_m) (_f | (_c<<1) | (_m<<2))
#define IDX_SLIPPERY 55
#define SF_SLIPPERY(_style) (_style.flags[IDX_SLIPPERY] & 0x1)
#define SC_SLIPPERY(_style) (_style.flags[IDX_SLIPPERY] & 0x2)
#define SM_SLIPPERY(_style) (_style.flags[IDX_SLIPPERY] & 0x4)
#define SET_SLIPPERY(_style,_f,_c,_m) (_style.flags[IDX_SLIPPERY] =
MERGE_OPTS(_f,_c,_m))

This solution does however introduce an additional offset when reading the
flags. !! can be used for each if you want to force a boolean result
(assuming thats whhy its done in the existing code):
#define SF_SLIPPERY(_style) !!(_style.flags[IDX_SLIPPERY] & 0x1)

This kind of solution isn't there most efficient (wastes bits and incurs
additional offsets when reading) but is simple to understand, maintain etc.

I did consider trying to share 2 options in one byte providing 4 bits per
option, but it seemed like that would introduce further processing when
reading and writing the data (additional shift most likely). I wasn't sure
this was worth it.

I guess the question really comes down to whether you think the complexity in
building the structures and bitfield addresses outweighs the wasted space and
additional processing of a simpler solution.

If you really want to go with generating code to allow referencing the fields
directly, heres my thoughts:

Create a C program to generate the structures from a datafile - all three
flag sets can use the same data file for field names which is beneificial
because each flag set would have the same order. Add the C program in at the
top of the dependency tree such that it must be compiled before anything
else. Then it can be run to generate the appropriate header with the
structure definition. It would be nice to separate these into a separate
flags.h header to minimise the other fields that must be generated. The
datafiles would list each field

Anyway thats my $.02
Dave

--
Dave, Diane & Kringle
http://www.geocities.com/SiliconValley/7499

---

From: Dominik Vogt <[email-masked]>
Date: Sun, 4 Aug 2002 12:15:50 +0200

> it would be a waste. Approximately how many options are we talking in this

The window structure currently has 144 flag members.  I didn't
care to cound how many of them are simple style switches.  Anyway,
the concept can be extended to a set of fixed choices, but if more
than one bit is involved, the bits may be located in different
bytes or even dwords.

> flags at once.

> To write three separate memory locations at once all the time
> is inefficient.

Well, I guess we can forget about efficience here since style
flags are rarely written.  It's done once when fvwm starts up and
whenever a new "Style" command is issued, but not at run time.  At
the moment, the waste of memory cause by using chars is roughly

   3 * 7 = 21 bytes for every 8 style flags per style
 +          7 bytes for every 8 "common" style flags per window

Putting all three flags in a single char would reduce the
overhead for style flags to 7 bytes per style.

> Do you agree that it would be better to store all three flags

Let me explain the meaning of the additional flags.  First, there
is the flag that sets the option's value (SF_... macros for
"Style Flag").  Second, there is a mask that indicates which flags
have been set at all and are not at their default value (SM_... =
"Style Mask").  This is used when merging styles.  Finally, there
is another mask that indicates which parts of a style were changed
since the style was evaluated (SC_... = "Style Changemask").  This
is used to decide which parts of a style have changed at runtime
to eliminate the overhead of evaluating options that have not
changed.

The mask and changemask are used in the style code to access the
whole style structure en-bloc as a character array without knowing
its internal layout.  For example, if you say

  Style A Foo, Bar
  Style A BarOff, Baz

The style code takes the logical "and" value of both style masks
to decide which parts of the first line have to be deallocated and
the sets the mask of the merged style to the logical "or" value.
This will be difficult to do when the flag, the mask and the
changemask reside in the same byte, along with other styles that
work differently in the same structure.

This whole logic is only part of styles.  The mask and changemask
are not needed in the window structure.

> additional processing of a simpler solution.

Well, there is another problem.  ANSI C doesn't prescribe how
bitfields are to be implemented by the compiler.  Theoretically,
there is no guarantee that a single bit switch is really mapped to
a hardware bit or that multi bit fields are placed in the same or
adjacent bytes.  The current code already relies on this
assumption.

> If you really want to go with generating code

Not really.  If something *has* to be generated at all, I'd prefer
a simple table instead of real C code.  That indroduces another
source of code inconsistencies, of course.

> to allow referencing the fields directly, heres my thoughts:
> 
> Create a C program to generate the structures from a datafile -

Hm.  It should also generate the access macros then.  Currently,
the macros assume that the flags structure is part of a style or
window structure, e.g.

  IS_STICKY(fw)

expands to

  (fw)->flags.common.is_sticky

This should be separated into several macros:

  #define FW_FLAGS(fw) ((fw)->flags)
  #define FW_CFLAGS(fw) FW_FLAGS(fw).common
  #define IS_STICKY(cf) (cf).is_sticky

==>

  IS_STICKY(FW_CFLAGS(fw))

> all three

Bye

Dominik ^_^  ^_^

 --
Dominik Vogt, [email-masked]
Reply-To: [email-masked]
--
Visit the official FVWM web page at <URL:http://www.fvwm.org/>.
To unsubscribe from the list, send "unsubscribe fvwm-workers" in the
body of a message to [email-masked].
To report problems, send mail to [email-masked]

---

From: Dave Trollope <[email-masked]>
Date: Mon, 05 Aug 2002 20:23:42 -0500

Hi Dominik

> work differently in the same structure.

Yes this certainly isn't worth it.

> adjacent bytes.  The current code already relies on this

Yes, thats why I was thinking of rewriting the get macros as well as the way the
data was stored. It would avoid this problem by hiding the implementation and not
trying to use the bitfields.

I think that redesigning the data storage is the best approach, and that means
removing the bitfields from the existing structures.

> source of code inconsistencies, of course.

Sorry, I didn't mean to generate code code, just C code tables as you are thinking.

>   #define IS_STICKY(cf) (cf).is_sticky

Yes I was thinking that this program should generate the macros too.

I think that if you remove the bitfields and replace them with a set of longword
arrays you can statically assign each bit of the array to a flag. Then you can use
the macro to hide the data implementation.

To simplify the creation of the flags, you could simply add the arrays to the
existing structures using a #define to set the array size.

Then from code, generate a .h with the macros that define the size of the arrays,
the macros to set and get each flag. The code can assign sequentially the bits in
the array and create the appropriate masks or macro to read a specific bit.

To really simplify the addition of new flags, a data file containing the flag and
symbol names can be used as the source, and all the macros can be created using
that symbol name. Then all that ever needs to happen is a new flag name gets added
to the data file, and bingo the arrays get bigger if needed, and all the macros to
set and get the data are automatically created in the header.

It can also create the C table with the long/bit offsets and name to allow bsearch
searching as you suggested although a long offset and mask would probably be
easier.

If you typedef the array type, you can also abstract that so that the tool can in
the future change the type of array if necessary. E.G. The tool may at some point
become smart enough to figure out if word reads are faster than long reads etc and
generate code to optimum performance by generating a different typedef and
assigning the flags differently.

I'm willing to write this code.

What do you think?

Cheers
Dave

---

From: Dave Trollope <[email-masked]>
Date: Mon, 05 Aug 2002 22:50:50 -0500

Hi

I've been having problems building 2.5.3 recently (month or two) and tonight
decided to figure it out.

At some point the $(Xft_LIBS) in LDADD of several Makefile.am files eg
fvwm/fvwm. On my system (cygwin) this causes a problem because -lfvwm is now
after -lXft. Flocale.c in libfvwm uses Xft.

Before submitting a patch for this, I was hoping someone could explain what
this change was made for so that I can make sure I don't undo whatever they
did!

Thanks a lot!
Dave

---

From: Olivier Chapuis <[email-masked]>
Date: Thu, 8 Aug 2002 18:37:16 +0200

> this change was made for so that I can make sure I don't undo whatever they

I did this "inversion" when I add Xft2 support. From the Changeog:

     * fvwm/Makefile.am:
     * libs/Makefile.am:
     Put $(Xft_CFLAGS) before $(X_CFLAGS) to be able to use an independent
     Xft2 library. Removed FT2 CFLAGS and LIBS

So -lfvwm should be before -lXft but -lXft should be before $(X_CFLAGS) ?
Patch welcome.

Regards, Olivier