Re: [RFC] Framebuffer rotation patch

[Michal Suchanek]

2010/2/11 Vladimir 'φ-coder/phcoder' Serbinenko <address@hidden>:
> Michal Suchanek wrote:
>> 2010/2/11 Vladimir 'φ-coder/phcoder' Serbinenko <address@hidden>:
>>
>>> Michal Suchanek wrote:
>>>
>>>> Hello
>>>>
>>>> Sending a preliminary framebuffer rotation patch.
>>>>
>>>> You can use videotest to see 4 tiles rotated from the same bitmap data.
>>>>
>>>>
>>>>
>>> +char leaf_data[] = { 0x00, 0x0f, 0xe0, 0x00,
>>> +                     0x00, 0x7f, 0xfc, 0x00,
>>> +                     0x01, 0xff, 0xff, 0x00,
>>> +                     0x03, 0xff, 0xff, 0x80,
>>> This is a blob. Could it be generated automatically at build time?
>>>
>>
>> How less of a blob it would be if it was included as a bitmap?
>>
>>
> It's not easily editable in current form.
>> This is just a shape used for the video tests.
>>
>> There are some X tools for working with bitmaps/pixmaps which could
>> generate this from a viewable file but they are usually not available
>> on Windows and other non-X platforms AFAIK.
>>
>>
> Using XBM is fine (it's easily editable in either gimp or emacs) and you
> should be able to
> #include "leaf1.xbm"

That would work if XBM and grub did not have opposite bit order. The
bytes are ordered the same but the bits are reversed.

>>> Could you split addition of videotests from the rest of the patch?

Yes, there should be no problem with that.

>>> -    unsigned int x;
>>> -    unsigned int y;
>>> -    unsigned int width;
>>> -    unsigned int height;
>>> +    int x;
>>> +    int y;
>>> +    int width;
>>> +    int height;
>>> Why do you need negative values?
>>>
>>
>> I don't need the negative values everywhere but this change was to
>> align the typing so that casts are not required.
>>
>>
> Perhaps few casts together with appropiate checks when casting is better
> than potentially exposing the whole code to the values it's not intended
> for.

How is it exposed to more unwanted values than now?
It uses the variables only to store the viewport dimensions and at
most adds a border around it. The unsigned integer is able to
represent values outside of the viewport as much as signed integers
are, only signed integer can represent values outside of viewport in
both directions. The unwanted values (if erroneously calculated which
does not seem to be the case here) are clipped by the viewport
clipping in video_fb.

On the other hand, there would be more than a few casts as the
variables are used multiple times and the interface now uses signed
integers.

>>> +/* Supported operations are simple and easy to understand.
>>> + * MIRROR  |  swap image across (around) the vertical axis
>>> + * FLIP    -  swap image across the horizontal axis - upside down
>>> + * SWAP    /  swap image across the x=y axis - swap the x and y coordinates
>>> It's just a D_8 group. Could you add a comment to functions what they do
>>> in group theoretical sense? It would make the code easier to follow and
>>>
>>
>> Obviously it is a group,
>
>> any set of transforms closed on composition is.
>>
>>
> Not true. Consider an example of empty set: it has no identity element.
> Less trivial counter-example: set of transformations: (x,y)->(kx,ky),
> 0<k<1. It's non-empty but has no identity element. If you replace < 1
> with <=1 you will have an identity element but no other element is
> invertible.

It depends on your exact definition of group which somewhat varies but
it is true that most definitions at least require the set to be
non-empty.

>>
>> If you have clearer explanation or more efficient code please share.
>>
>>
> I was thinking of using 2 generators instead of 3:
> 1) standard generators: s=rot90 or rot270, t=any reflection. Then all
> elements are s^k or s^k*t. It makes computation of composition easier.
> Rules on generators are:
> s^n=t^2=1
> tst=s^{-1}
> 2) or using 2 reflections. E.g. u=| and v=/. You already figured how to
> generate with u=|, v=/, w=-
> But w=uvuv
> Then rules of computation are:
> u^2=v^2=(uv)^4=1

This might be mathematically optimal but how that maps to actual efficient code?

In my view the v (and s) operations are expensive so I want to avoid
them if possible.

This requires that both u and w be in the chosen set of generators
because otherwise use of v or s twice is required to get one from the
other. Using (u or w) and v as the two basic operations additionally
requires composing generators in non-fixed order to get all the 8
possible combinations.

The other reason for having 3 generators is clear and efficient
reperesentation of the 8 possible transformations. They are
represented as bits in the bitmap where each bit specifies if the
particular basic transform is included or not but they are always
applied in fixed order and at most once.

Compare this to your representation of s^k,s^k*t where k is 0..3.
Depending on representation the composition and inversion rules might
still be somewhat non-trivial in actual code, using two reflections
which require multiple applications of the two generators in
particular order would lead to even more "interesting" code.

>>> +static inline long
>>> +grub_min (long x, long y)
>>> +{
>>> +  if (x > y)
>>> +    return y;
>>> +  else
>>> +    return x;
>>> +}
>>> +
>>> Same here
>>> +
>>> +  int transform;
>>> I would prefer an enum
>>>
>>
>> This is a bit field. How does it transform into an enum?
>>
> enum my_bitfield
> {
>  MY_BITFIELD_NONE=0,
>  MY_BITFIELD_BIT0 = 1 << 0,
>  MY_BITFIELD_BIT1 = 1 << 1,
>  MY_BITFIELD_BIT2 = 1 << 2
> };

The whole point of a bitfield is to have values like
MY_BITFIELD_1_AND_2 = MY_BITFIELD_BIT1 | MY_BITFIELD_BIT2 which enum
does not allow.

Thanks

Michal