On Sat, Aug 03, 2002 at 10:53:21PM -0500, Dave Trollope wrote:
> 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?
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.
> 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.
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
> 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.
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.
> 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.
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
> 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
>
> Dominik Vogt wrote:
>
> > 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, [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
--
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 PROTECTED]
To report problems, send mail to [EMAIL PROTECTED]
