struct-type entanglement, crazy idea? (myC)

[DiTBho]

It all started with the need to write an extremely fast and flexible algorithm to search for patterns in a large block of memory.
I need it for hacking the firmware of the rb532a router; patterns are hex-blocks, and the search key needs to use wildcards.

Code: [Select]

hex_search_ans_t hex_search
(
    p_o_lineadv_t p_o_blk,
    p_o_lineadv_t p_o_key,
    p_o_lineadv_t p_o_msk
)

since the search key must also work with wildcards, I combined three algorithms

• evaluates the shortest subkey that does not contain wildcards: f(key, msk) -> toe
• quickly searches for the position of the first occurrence of toe, which is presumably assumed as a candidate for the solution
• classic pattern matching that uses the original search { key, msk } to confirm/reject the candidate

Code: [Select]

typedef struct
{
    p_char_t p;     /* point to the body */
    uint32_t i0;    /* starting position */
    uint32_t i1;    /* ending   position */
    uint32_t size;  /* body size */
} o_lineadv_t;

All the algorithms uses a special type, which is a superset of safestring and can also handle array of hex chars

I decided to split the searching key into two things, an array containing all the hex values of key and a mask containing nothing but the wildcards.
This way, it's super clean and flexible, but these two arrays must be of the same lenght, and use the same offset.

Code: [Select]

    o_lineadv_copy(p_o_key, p_o_toe);  /* source -> target */
    l0_key_toe0_get(p_o_toe, p_o_msk); /* case toe begins      with a wildcard */
    l0_key_toe1_get(p_o_toe, p_o_msk); /* case toe first char after a wildcard */

toe is dynamically created as (field-by-field) copy of o_key, then it's modified.

Code: [Select]

    /*
     * key and msk must be intertwined
     * in practice their structures must have the same values
     * except the field which points to two different bodies
     */
    is_ok = o_lineadv_is_comparable(p_o_key, p_o_msk);
    if (is_ok isEqualTo True)
    {
        ...
    }
    else
    {
        panic(module, fid, "key and msk must be intertwined");
        ans.i0       = p_o_msg->i0;
        ans.is_valid = False;       
    }

In practice their structures must have the same values except the field which points to two different bodies!
The first version of the library was full of these checkpoints, then... I asked myself if they could be avoided!

And ...

... and that's how I got the idea to create a new language-feauture.
Something that I don't even know if anyone has already thought of or if it's useful... but experimenting it seems to be!

Code: [Select]

entanglement o_lineadv_t
{
    p:    no;  /* will not be shared */
    i0:   yes; /* will be shared */
    i1:   yes; /* will be shared */
    size: yes; /* will be shared */
} o_key, o_msk;
p_o_lineadv_t p_o_key;
p_o_lineadv_t p_o_msk;

p_o_key = get_address(o_key);
p_o_msk = get_address(o_msk);

with this weird variable definition, these two variables  won't be implemented as independent structs, for a total of 2x(4x4) = 32 bytes,
but rather with an unique struct that shares most of the fields, for a total of 2x4+(3x4)=20bytes.

So, not only do you no longer have to worry about whether key and mask are perfectly compatible, but they also consume less memory!

Ok, not too much here, but in my opinion, the real advantages come with polymorphic programming!
With this feature you save a lot of code and RAM, making two objects share a large part of the methods and structures that are common.


Ummm, too crazy? 


(already implemented as alpha version, it's working!)

[MarginallyStable]

This is easy in c++, just declare the shared members static. You could have a bit more flexibility by utilizing inheritance.

[DiTBho]

This is easy in c++, just declare the shared members static. You could have a bit more flexibility by utilizing inheritance.

that's nice to hear, because it means it was not just a crazy idea 

Can you give an example? I am very rusty with C++
I mean, I programmed something "academic" in C++ when I was a student,
but many many years ago.

[SiliconWizard]

The usual approach in C would be to pass around a separate struct with the common content.
If you want the convenience of "embedding" this common content inside several distinct structs, you'd define a pointer to it in said structs.
Essentially, what you suggest here is some sugar coating for that.

Whether it's a good idea from a language standpoint, I'm unsure. Trying to figure it out.
Yes, in C++ you can do that with static members. C doesn't support the static qualifier for struct members.

Having some shared state encapsulated like this can be useful, but I'm again not sure it's a good design idea. That would probably make the "functional" crowd cringe.

[DiTBho]

The usual approach in C would be to pass around a separate struct with the common content.
If you want the convenience of "embedding" this common content inside several distinct structs, you'd define a pointer to it in said structs.

In this specific case, in C/89 I would use something like this

Code: [Select]

typedef struct
{
    p_char_t p[2];  /* point to the body, use p[0] for key, use p[1] for msk */
    uint32_t i0;    /* starting position, shared */
    uint32_t i1;    /* ending   position, shared */
    uint32_t size;  /* body size, shared */
} o_lineadv_key_msk_t;

but umm, this issue came up after I wrote a string-pattern search function, and then extended it to hex patterns.
The skeleton was already designed, and didn't want to modify it too much
So I introduced the second msk array and make sure it was perfectly intertwined with key.

What happens if they are not intertwined?

well... high probability that one of the two algorithms that uses them will throw an exception
myC is very strict if you exceed the upper or lower limit of an array.

[MarginallyStable]

Can you give an example?

Code: [Select]

#include <stdio.h>

typedef struct EXAMPLE_T {
    int some_unique_variable;
    static int some_shared_variable;
} example_t;

//instantiate shared variable
int EXAMPLE_T::some_shared_variable = 0;

int main(void)
{
    EXAMPLE_T a,b;
    a.some_unique_variable = 1;
    a.some_shared_variable = 10;
    b.some_unique_variable = 2;
    b.some_shared_variable = 11;

    printf("A: %i %i   B: %i %i\n", a.some_unique_variable,
    a.some_shared_variable,
    b.some_unique_variable,
    b.some_shared_variable);

    return 0;
}

/*
output:
A: 1 11   B: 2 11
*/

[DiTBho]

To keep or to drop, this is my problem.

[Nominal Animal]

I often use structs with anonymous union as a payload, for example
    typedef struct node {
        struct node *below;
        struct node *above;
        union {
            struct payload_foo  foo;
            struct payload_bar  bar;
        };
    } node;
for trees that use the same navigation routines but different payload types.

Often, but not always, the payload types share the initial member(s) indicating the type of the payload.  (C rules are such that any of the unions can be used to access the common initial member.)  In some cases, the type of the payload is implicit, for example whether both pointers are NULL (a leaf node) or not (an inner node).

That is similar to yours, except yours splits it into separate types based on the union members accessible, if I understood you correctly.

As MarginallyStable mentioned, in C++ and other object-oriented languages the shared parts would be in a base class, with a derived subclass for each of the union types.

The C form has additional downsides like the structure size being dictated by the largest member in each union, and all unions being always accessible (and effectively reinterpreting the shared underlying storage for all union members).

Is it useful?  I dunno.  The standard C alternative is to use different structure types, but with a specific same structure as the first member.  As long as the structures' alignments are the same –– you can enforce that by making the first member an union with one type that initial structure, and the other a max_align_t  dummy to ensure it has maximum scalar alignment ––, because no padding is allowed at the start of a structure, the common initial member is accessible via any of those types (if we ignore some strict aliasing rules for a bit).

All the options here have upsides and downsides.  The question I'd base my decision on would be Is this useful in practice?  Will this make my code more robust?  Will this make my code easier to debug and maintain in the long term?.  Other than that,

[DiTBho]

All the options here have upsides and downsides.  The question I'd base my decision on would be Is this useful in practice?  Will this make my code more robust?  Will this make my code easier to debug and maintain in the long term?.  Other than that,

I'm using it in a couple of projects, and it seems very useful because, related to algorithms that need to operate with two paired arrays/objects, it makes what I write less "error-prone", in the sense that I let the compiler do the checks that I would otherwise have to implement, when then out of laziness, or tiredness, I end up leaving them out.

Code: [Select]

entanglement o_lineadv_t
{
    p:    no;  /* will not be shared, don't check the size of what p points to */
    i0:   yes; /* will be shared */
    i1:   yes; /* will be shared */
    size: yes; /* will be shared, this is just a value, it's not checked against the size of what p points to */
} o_key, o_msk;

However, I changed the mechanism a bit.

Code: [Select]

entanglement o_lineadv_t
{
    p:    { me = no, dereference(me)'propererty = yes };  /* p will not be shared, check the same properperty'size of what p points to */
    i0:   yes; /* will be shared */
    i1:   yes; /* will be shared */
    size: yes; /* will be shared, this is just a value, it's not checked against the size of what p points to */
} o_key, o_msk;

In the case of pointers it did not do any check, now I added the ability to check that the properties are identical.
One of the very important properties is the size of the buffer to which it points.

Paired buffers must be of the same size