60

I was confronted with a tricky (IMO) question. I needed to compare two MAC addresses, in the most efficient manner.

The only thought that crossed my mind in that moment was the trivial solution - a for loop, and comparing locations, and so I did, but the interviewer was aiming to casting.

The MAC definition:

typedef struct macA {
   char data[6];
} MAC;

And the function is (the one I was asked to implement):

int isEqual(MAC* addr1, MAC* addr2)
{
    int i;

    for(i = 0; i<6; i++)
    {
        if(addr1->data[i] != addr2->data[i]) 
            return 0;
    }
    return 1;
}

But as mentioned, he was aiming for casting.

Meaning, to somehow cast the MAC address given to an int, compare both of the addresses, and return.

But when casting, int int_addr1 = (int)addr1;, only four bytes will be casted, right? Should I check the remaining ones? Meaning locations 4 and 5?

Both char and int are integer types so casting is legal, but what happens in the described situation?

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Itzik984
  • 15,968
  • 28
  • 69
  • 107
  • 1
    Sorry, but who said you had to do any int casting? he wanted you to do char comparison – Noam Rathaus Dec 31 '13 at 14:46
  • 1
    Is this meant for an embedded system? – Michael Hampton Dec 31 '13 at 18:25
  • 1
    since the size of a MAC is 48 bits (6 bytes) by definition, it makes sense to #define MAC_SIZE (6). – ChuckCottrill Dec 31 '13 at 18:58
  • 4
    For what it's worth, when I ask this sort of question -- which I try not to! -- I'm generally not looking for a single answer but for what questions the applicant asks about the constraints and priorities, and whether they can discuss why they chose one answer rather than another. – keshlam Jan 01 '14 at 05:20

11 Answers11

115

If he is really dissatisfied with this approach (which is essentially a brain fart, since you aren't comparing megabytes or gigabytes of data, so one shan't really be worrying about "efficiency" and "speed" in this case), just tell him that you trust the quality and speed of the standard library:

int isEqual(MAC* addr1, MAC* addr2)
{
    return memcmp(&addr1->data, &addr2->data, sizeof(addr1->data)) == 0;
}
  • actually `memcmp` is an intrinsic function (in most of compilers), so it's rather "quality of optimizer" – Abyx Dec 31 '13 at 14:49
  • @Abyx Yup, or that. And it's almost surely implemented in terms of [similar undefined behavior](http://stackoverflow.com/questions/20312340/why-does-this-implementation-of-strlen-work). –  Dec 31 '13 at 14:49
  • 1
    @H2CO3: Well, it's implemented in terms of machine behaviour that the compiler knows about. It doesn't have to *tell* you, but it knows. – Kerrek SB Dec 31 '13 at 14:50
  • 1
    @KerrekSB "undefined" as far as the standard knows. Of course it's something meaningful on the actual, particular implementation. –  Dec 31 '13 at 14:51
  • 1
    That said, I'd be curious to comparing the result for `memcmp` and comparing `uint64_t`s. The former needs a bunch of branchings, I suppose, since there's no alignment guarantees on the pointers... – Kerrek SB Dec 31 '13 at 14:51
  • 20
    @H2CO3, you can write a post rewriting an OS i/o sub-system and garner 35 points. Smack down an interviewer - a process everyone inherently hates - and 150! – Duck Dec 31 '13 at 15:00
  • 2
    @Duck The sorry state of software development! –  Dec 31 '13 at 15:01
  • @haccks Still better than the gray ribbon, huh? :D –  Dec 31 '13 at 15:04
  • 4
    @H2CO3: While true that `data` is an array and not a pointer, `memcmp(addr1->data, addr2->data, sizeof(addr1->data))` is still correct (due to decay), no? – legends2k Dec 31 '13 at 15:06
  • @H2CO3; That ribbon is message that there are also some grey sheds in life. And that eagle represents that "do not worry" :P – haccks Dec 31 '13 at 15:07
  • 4
    @haccks: To me, the eagles only represent that "you can log in anytime, but you can never log out"... – Kerrek SB Dec 31 '13 at 15:17
  • @KerrekSB; Man! Not bad. I have not logged out since last 3 months. :) – haccks Dec 31 '13 at 15:19
  • Curious as why you didn't suggest `return memcmp(addr1, addr2, sizeof(*addr1)) == 0`? Maybe 6 of 1 - half a dozen of the other. – chux - Reinstate Monica Dec 31 '13 at 20:51
  • 4
    @chux Because there may be padding at the end of the struct which contains unspecified padding bytes. That would result in false negatives. –  Dec 31 '13 at 21:32
  • So the `sizeof(*addr1)` may be greater than `sizeof(addr1->data)` - interesting. – chux - Reinstate Monica Dec 31 '13 at 21:53
  • @H2CO3 Is `&addr1->data + 1` the same as `addr->data + 1`? – ajay Dec 31 '13 at 22:44
  • Then how can `memcmp` function behave the same in both cases: in your answer and the one suggested by @legends2k – ajay Dec 31 '13 at 22:46
  • @ajay Because `&addr1->data` points to the same place where the pointer which `addr->data` decays into points. It's just their types that differ. –  Dec 31 '13 at 22:49
  • Ok. I got it. Was wondering how memcmp advances to the next byte for comparison and thought it may be using the type information of the pointers passed to it but seems like it doesn't. Could you please provide some pointers regarding this :) – ajay Dec 31 '13 at 22:53
  • 2
    @Lee But again, speculation is pointless. Only benchmarked code can be optimized thoughtfully. The rest is just BS. –  Dec 31 '13 at 23:19
  • @Lee So are you basically asserting that I have no idea what C code looks like when it's disassembled (actually, rather "assembled")? Because then you're on the wrong track. Also, "speculation" because we don't know the context OP will use this code in. If it's inside a tight loop, it's probably worth optimizing. But who knows? –  Dec 31 '13 at 23:43
  • 1
    @ajay [`memcmp`](http://en.cppreference.com/w/cpp/string/byte/memcmp)'s doc says it reinterprets the `void*`s as arrays of `unsigned char`s and advances by bytes (the 2nd param). – legends2k Dec 31 '13 at 23:45
  • 5
    @Lee Huh what? "memcmp of two ints is inefficient" is not true as-is (see the discussion above). Also, "sane code" == code that's not unnecessarily "clever" and does not rely on UB if not needed. One property of sane code is the reliance on the standard library. You see now? –  Dec 31 '13 at 23:55
  • @H2CO3; *But as mentioned, he was aiming for casting.* : Where is casting in this answer ? – haccks Jan 01 '14 at 16:45
  • 1
    @haccks Inside `memcmp()` :P The thing is, what the interviewer **really** wanted is an efficient implementation. He though that it was done by aliasing through pointers to different types. However, that is wrong, and I've pointed out a different "efficient" [I hate this word] solution. –  Jan 01 '14 at 16:56
  • On first read of this question I thought about explicit cast. I know parameters of `memcmp` are of `void *`. Then today again I came to this question and read your answer again and found its implicit casting here. – haccks Jan 01 '14 at 17:13
  • 1
    @haccks No. There's no such thing as an implicit cast. The word "cast" is used exclusively for "explicit type conversion". I didn't state the cast occurs when one passes the arguments to `memcmp()`. It is most probably *inside* `memcmp()` itself. But that's of course not obligatory (I wouldn't even implement `memcmp()` like that). –  Jan 01 '14 at 17:14
  • Oh yes. cast is used for explicit conversion. But I still do not understand what is the need for casting address here (as interviewer expecting) ? And still there is no casting only type conversion by `memcmp` :) – haccks Jan 01 '14 at 17:23
  • 2
    @haccks "But I still do not understand what is the need for casting address here (as interviewer expecting) ?" - neither do I. A cast is not necessary, and what the interviewer presumably expected is **wrong** because it causes undefined behavior. –  Jan 01 '14 at 17:25
  • Could you give me the reference where it is mentioned about UB on casting? I need that to use in future on SO :) – haccks Jan 01 '14 at 17:28
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/44280/discussion-between-h2co3-and-haccks) –  Jan 01 '14 at 17:39
  • 2
    My hunch was that calling memcmp is not going to be optimal 1) b/c of function call overhead. 2) b/c you can't expect code written to handle the general case to be faster than code that was written knowing it was only going to ever compare six bytes. I got curious and decided to look at the optimized x64 this generates from VS2013. It turns out the function call is inlined, but a byte by byte comparison is generated in a fully rolled loop (thats 6 branches, 6 single-byte comparisons). So any making fun of the interviewer aside, this code does not satisfy his requirements particularly well. – Apriori Jan 02 '14 at 07:38
  • 1
    @Rich: Wrong. MSVC2012 compiles that to a 4 bytes then 2 bytes comparison for me. –  Jan 21 '14 at 10:59
  • @M28 My apologies for the misinformation, yes you are correct. When I looked at it before I must've had some optimization options off by mistake. I tried it again, below is the optimized x64 from VS2013. It generates more jumps than needed but otherwise not bad. mov ecx,dword ptr [rsp+20h] // load 4 bytes from a sub ecx,dword ptr [rsp+28h] // subtract 4 bytes from b jne 000000013F751329 // if != jump to xor movzx ecx,word ptr [rsp+24h] // load bytes 4 and 5 of a movzx eax,word ptr [rsp+2Ch] // load bytes 4 and 5 of b sub ecx,eax xor edx,edx test ecx,ecx – Apriori Jan 24 '14 at 16:44
46

If your interviewer demands that you produce undefined behavior, I would probably look for a job elsewhere.

The correct initial approach would be to store the MAC address in something like a uint64_t, at least in-memory. Then comparisons would be trivial, and implementable efficiently.

haccks
  • 104,019
  • 25
  • 176
  • 264
Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
  • maybe he wanted me to figure out this is an undefined behaviour? :) i had no idea what answer to give him. – Itzik984 Dec 31 '13 at 14:42
  • 1
    @Itzik984: It depends. If you had said, "treating this array as an integer would be undefined behaviour", I guess that would have been OK. – Kerrek SB Dec 31 '13 at 14:43
  • 8
    @ltzik984 No, most probably he has no idea that this is undefined behavior. –  Dec 31 '13 at 14:43
  • Anectdote: During my first job interview I was given code to comment on. I gave five independent reasons for why the code had undefined behaviour and could be doing anything. (I got the job, despite that.) – Kerrek SB Dec 31 '13 at 14:44
  • and in your solution, do you mean something like: uint64_t laddr1 = addr1; ? – Itzik984 Dec 31 '13 at 14:45
  • @H2CO3 why downvoting? – Itzik984 Dec 31 '13 at 14:47
  • @FilipeGonçalves Fair enough :D –  Dec 31 '13 at 14:49
  • I did downvote that. Because I don't like the idea of using uint64 for a 48-bit value. Also bitcasting wouldn't lead to UB. – Abyx Dec 31 '13 at 14:49
  • You can use type punning to do some quick transforms for a range of purposes. But you only get the desired behavior reliably when the types are intrinsically the same size. A char[4] or a char[8] could be punned to 32/64 bit ints for comparison. Equality doesnt care about endianness, unfortunately it might care about padding with undefined and potentially different contents. – RichardPlunkett Dec 31 '13 at 14:51
  • 4
    @Abyx: Why not post as an answer what you think should be done, and we can see whether it's UB? – Kerrek SB Dec 31 '13 at 14:55
  • 5
    @Abyx **It does lead to UB.** At the very moment you dereference the pointer to an incompatible type. –  Dec 31 '13 at 14:59
  • @H2CO3 ok, maybe it is UB in C. I don't know C so I'll believe you that it's UB. – Abyx Dec 31 '13 at 15:12
  • 16
    @Abyx: You don't know C, but you're voting me down for not suggesting something that would be wrong? :-S – Kerrek SB Dec 31 '13 at 15:14
  • @KerrekSB I still disagree that `MAC` should use `uint64_t`. Comparisons are already trivial with `memcmp` and you'll get problems when you'll need to read or write that MAC from `char[6]`, e.g. in a network packet. – Abyx Dec 31 '13 at 15:17
  • I'm going to agree with Abyx here and say that `MAC` shouldn't be a `uint64_t`. If you do that, it's easier to accidentally treat data as a number(you shouldn't be doing math on a MAC address, should you?). It will fit, but if you need to extract that data on a machine that is different endianess you now have all sorts of bitshifting/bitmasking problems to worry about. – rm5248 Dec 31 '13 at 22:23
  • 6
    @rm5248: A MAC address *is* just a number. It's like if you insisted on designing your own 21-bit integer for textual characters, rather than using the sane `char32_t`. – Kerrek SB Dec 31 '13 at 23:15
16

Cowboy time:

typedef struct macA {
   char data[6];
} MAC;

typedef struct sometimes_works {
   long some;
   short more;
} cast_it

typedef union cowboy
{
    MAC real;
    cast_it hack;
} cowboy_cast;

int isEqual(MAC* addr1, MAC* addr2)
{
     assert(sizeof(MAC) == sizeof(cowboy_cast));  // Can't be bigger
     assert(sizeof(MAC) == sizeof(cast_it));      // Can't be smaller

     if ( ( ((cowboy_cast *)addr1)->hack.some == ((cowboy_cast *)addr2)->hack.some )
       && ( ((cowboy_cast *)addr1)->hack.more == ((cowboy_cast *)addr2)->hack.more ) )
             return (0 == 0);

     return (0 == 42);
}
Glenn Teitelbaum
  • 10,108
  • 3
  • 36
  • 80
  • I am not sure how you gain much here using the union. I mean if you have alignment issues with your MAC, then you will still have them, Meanwhile if you dont have alignement issues, then you are still relying on the sizeof(MAC) being 6 and/or the padding being in the right place. It seems like the same risks you are running casting the MAC/data point directly. – RichardPlunkett Dec 31 '13 at 17:02
  • @RichardPlunkett I included the cowboy cast because it does sometimes come up in interviews, or legacy code, and whether it has benefits over direct cast or `memcmp` is not as important as knowing of this approach, and most likely avoiding it. But if you haven't seen it, you can't say why. – Glenn Teitelbaum Dec 31 '13 at 17:08
  • 3
    @RichardPlunkett No. Unions guarantee correct alignment. Since C99, union-based type punning is legal (it's no longer UB), unlike aliasing through pointers to incompatible types. –  Dec 31 '13 at 21:34
  • Shouldn't that be `typedef struct sometimes_works { uint32_t some; uint16_t more; } cast_it;` for portability? – tomlogic Jan 01 '14 at 01:11
  • 1
    @H2CO3, I dont think a union does guarantee alignment here. I mean if you declare a cowboy_cast variable, it will be aligned correctly for this, but you cant guarantee any miscellaneous MAC struct will have correct alignment for a cowboy_cast, and we are passed a MAC pointer. – RichardPlunkett Jan 01 '14 at 01:47
14

There is nothing wrong with an efficient implementation, for all you know this has been determined to be hot code that is called many many times. And in any case, its okay for interview questions to have odd constraints.

Logical AND is a priori a branching instruction due to short-circuit evaluation even if it doesn't compile this way, so lets avoid it, we don't need it. Nor do we need to convert our return value to a true bool (true or false, not 0 or anything that's not zero).

Here is a fast solution on 32-bit: XOR will capture the differences, OR will record difference in both parts, and NOT will negate the condition into EQUALS, not UNEQUAL. The LHS and RHS are independent computations, so a superscalar processor can do this in parallel.

int isEqual(MAC* addr1, MAC* addr2)
{
    return ~((*(int*)addr2 ^ *(int*)addr1) | (int)(((short*)addr2)[2] ^ ((short*)addr1)[2]));
}

EDIT
The purpose of the above code was to show that this could be done efficiently without branching. Comments have pointed out this C++ classifies this as undefined behavior. While true, VS handles this fine. Without changing the interviewer's struct definition and function signature, in order to avoid undefined behavior an extra copy must be made. So the non-undefined behavior way without branching but with an extra copy would be as follows:

int isEqual(MAC* addr1, MAC* addr2)
{
    struct IntShort
    {
        int   i;
        short s;
    };

    union MACU
    {
        MAC addr;
        IntShort is;
    };

    MACU u1;
    MACU u2;

    u1.addr = *addr1; // extra copy
    u2.addr = *addr2; // extra copy

    return ~((u1.is.i ^ u2.is.i) | (int)(u1.is.s ^ u2.is.s)); // still no branching
}
Apriori
  • 2,308
  • 15
  • 16
  • 1
    Can I ask why is this not undefined b., such as this http://stackoverflow.com/a/20859133/2327831? Even if you assume that int is sizeof 4 and short is 2, you are still casting and dereferencing an incompatible type. – this Jan 19 '14 at 14:14
  • @self I believe this really isn't undefined behavior, but rather implementation defined behavior. That is, it is well defined on a per platform basis. However after much searching I haven't found anything official-looking that address this. If you read the first comment here, this suggests the same thing http://stackoverflow.com/q/11373203/3100771 even though this is talking about unions. One could just as easily define a function-scope union type and do the operation in terms of that. I would be very interested to see a full list of implementation defined behavior in C++; Google failed me. – Apriori Jan 20 '14 at 03:06
  • 1
    It is undefined behavior because you're breaking pointer aliasing rules. There are compilers that won't let you get away with that and just optimize the whole thing away without warning you. You should use an union. Even though it's still a violation of the spec, most compilers support it and don't consider it undefined behavior. –  Jan 21 '14 at 11:08
  • @M28 Type punning with unions is not a violation of semantics. It has well-defined behavior in C99 and later. –  Jan 28 '14 at 09:45
  • @self. what you are doing in this answer leads to UB because you are dereferencing a pointer to incompatible type. –  Jan 28 '14 at 09:46
  • @H2CO3 Did you mean this question is UB, the one I linked, or both? It seems to me that both are UB. – this Jan 28 '14 at 11:25
  • @self. Ugh, sorry, I was direcring this towards Rich. This answer right here is UB; I haven't seen the link (on my phone, will check at home) –  Jan 28 '14 at 11:51
  • @self. Update: I've looked at the other answer, and yes, that is UB as well, they're doing essentially the same thing. –  Jan 28 '14 at 12:06
  • @H2CO3 Tnx for confirmation. Since no answer used an union correctly, I wrote my own. Could you critique it? http://stackoverflow.com/a/21406104/2327831 – this Jan 28 '14 at 12:56
  • 1
    @self. Your answer is fine, upvoted. I'm not sure you need the additional `struct`, though (`uint16_t w[3];` would've been enough). –  Jan 28 '14 at 14:07
  • It's hard (impossible) to use unions correctly and provide the fastest possible implementation when the interviewer didn't define the struct that way; or at least before the optimizer has it's way. The point of the answer was to show how this could be done without branching, and without conversion to bool (i.e 0x18A73C is true). Microsoft's compilers at least handle this fine, and converting such a thing to use unions instead is trivial. However, for clarity I've updated my answer to include an alternate no-UB version. – Apriori Jan 28 '14 at 21:35
4

This would work on most systems,and be faster than your solution.

int isEqual(MAC* addr1, MAC* addr2)
{
    return ((int32*)addr1)[0] == ((int32*)addr2)[0] &&  ((int16*)addr1)[2] == ((int16*)addr2)[2];
}

would inline nicely too, could be handy at the center of loop on a system where you can check the details are viable.

RichardPlunkett
  • 2,998
  • 14
  • 14
  • 13
    And thus the hydra of Undefined Behaviour rears several of its many heads. – Kerrek SB Dec 31 '13 at 15:01
  • 3
    While true, it would be worth mentioning that this relies on undefined behavior. –  Dec 31 '13 at 15:01
  • Not the interviewer, and I wouldnt be happy with this type of code in most circumstances, but it the kind of things some people think is a good idea. – RichardPlunkett Dec 31 '13 at 15:03
  • Also, I have done way worse things then this when asked to squeeze out an extra half a cycle from an inner loop when I was allowed to know which system I was writing for. – RichardPlunkett Dec 31 '13 at 15:05
  • 3
    At least redefine the structure as a union with uint16_t[3] or uint32_t+uint16_t if extra padding is allowable and compare those fields to avoid UB. Of course many compilers are sufficiently clever to appropriately optimize fixed-size memcmp(), especially if given an alignment hint – doynax Dec 31 '13 at 15:06
  • @doynax Yup, union-based type punning should be safe since C99 (it has implementation-defined results compared to UB). –  Dec 31 '13 at 15:07
  • 2
    The `int16` comparison should be on the third element (index 2), not the second. – Benjamin Lindley Dec 31 '13 at 15:08
  • 1
    @H2CO3: Huh. I thought char aliasing was well-defined special-case. I've been wrong in the past though.. – doynax Dec 31 '13 at 15:08
  • 1
    @doynax: That's the other way round! – Kerrek SB Dec 31 '13 at 15:09
  • its a POD, they are usually pretty well behaved, with the only question typically being whether this struct is 6 bytes or 8, and if 8, where your 6 bytes are. @Ben, yep thanks – RichardPlunkett Dec 31 '13 at 15:11
  • @KerrekSB: Curious, I'll have to do some digging in the standards. How are you supposed to reimplement memcpy in that case? – doynax Dec 31 '13 at 15:11
  • @doynax The only way that doesn't cause UB is copying character by character. –  Dec 31 '13 at 15:14
  • 1
    @doynax: That's precisely the other way round: You *can* interpret every object as an array of characters. But you cannot interpret any old array of characters as an arbitrary object. `memcpy` only needs to do the former. – Kerrek SB Dec 31 '13 at 15:15
  • 2
    I'd add `_Static_assert(sizeof(MAC) == 6 && sizeof(int32) == 4 && sizeof(int16) == 2, "we support only sane architectures");` – Abyx Dec 31 '13 at 15:24
  • @KerrekSB: I think I see the distinction, and obviously plucking out and comparing the value in the form of a pointer may even fail in practice. Are you saying it is even implementation-defined behavior to craft an uint16_t, where every bit pattern is valid, from two arbitrary characters unless they originated (say during deserialization) from an uint16_t in the first place? Assuming CHAR_BIT = 8 – doynax Dec 31 '13 at 15:29
  • @doynax: Correct. The only thing that's an `int` is an `int`. If you want an `int`, make an `int`. If you want to talk to the individual bytes of the `int`, you can treat it as an array of characters. But it has to be an `int`. – Kerrek SB Dec 31 '13 at 15:32
  • @Abyx yep, those would be good things to add, tho I might be using #if rather/in addition to static asserts. Never write horribly unportable code without portable code nearby to call when needed. – RichardPlunkett Dec 31 '13 at 15:45
  • @KerrekSB: That does seem a subtle distinction when we know that the characters stored must be a valid and unique representation of one uint16_t value, that certain character pairs (e.g. memset 0) have well-defined values, and that there are no aliasing issues. Is the idea that the compiler may analyze the code and reason out that the bit-pattern ultimately originated from another type and get confused? (I'm sorry to carp on about semantics but I'm genuinely curious.) – doynax Dec 31 '13 at 15:58
  • 3
    @doynax: The most obvious problem is that the platform may require aligned storage for integer operations, so if your character pointer doesn't satisfy that, your CPU may raise an exception. x86 doesn't have that problem, but there are other platforms that do. – Kerrek SB Dec 31 '13 at 16:16
  • @KerrekSB: That bit I do get, actually. Which was why I suggested redefining the MAC structure as a union of char[6] and uint16_t[3] – doynax Dec 31 '13 at 16:24
3

Non-portable casting solution.

In a platform I use (PIC24 based), there is a type int48, so making a safe assumption char is 8 bits and the usual alignment requirements:

int isEqual(MAC* addr1, MAC* addr2) {
  return *((int48_t*) &addr1->data) == *((int48_t*) &addr2->data);
}

Of course, this is not usable on many platforms, but then so are a number of solutions that are not portable either, depending on assumed int size, no padding, etc.

The highest portable solution (and reasonably fast given a good compiler) is the memcmp() offered by @H2CO3.

Going to a higher design level and using a wide enough integer type like uint64_t instead of struct macA, as suggested by Kerrek SB, is very appealing.

chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
1

To do type punning correctly you have to use an union. Otherwise you will break the rules strict aliasing which certain compilers follow, and the result will be undefined.

int EqualMac( MAC* a , MAC* b )
{
    union
    {
        MAC m ;
        uint16_t w[3] ;

    } ua , ub ;

    ua.m = *a ;
    ub.m = *b ;

    if( ua.w[0] != ub.w[0] )  
        return 0 ;

    if( ua.w[1] != ub.w[1] )
        return 0 ;

    if( ua.w[2] != ub.w[2] )
        return 0 ;

return 1 ;
}

According to C99 it is safe to read from an union member that is not the last used to store a value in it.

If the member used to read the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called "type punning"). This might be a trap representation.

this
  • 5,229
  • 1
  • 22
  • 51
0

You have a MAC structure (which contains an array of 6 bytes),

typedef struct {
    char data[6];
} MAC;

Which agrees with this article about typedef for fixed length byte array.

The naive approach would be to assume the MAC address is word aligned (which is probably what the interviewer wanted), albeit not guaranteed.

typedef unsigned long u32;
typedef   signed long s32;
typedef unsigned short u16;
typedef   signed short s16;

int
MACcmp(MAC* mac1, MAC* mac2)
{
    if(!mac1 || !mac2) return(-1); //check for NULL args
    u32 m1 = *(u32*)mac1->data;
    U32 m2 = *(u32*)mac2->data;
    if( m1 != m2 ) return (s32)m1 - (s32)m2;
    u16 m3 = *(u16*)(mac1->data+4);
    u16 m2 = *(u16*)(mac2->data+4);
    return (s16)m3 - (s16)m4;
}

Slightly safer would be to interpret the char[6] as a short[3] (MAC more likely to be aligned on even byte boundaries than odd),

typedef unsigned short u16;
typedef   signed short s16;

int
MACcmp(MAC* mac1, MAC* mac2)
{
    if(!mac1 || !mac2) return(-1); //check for NULL args
    u16* p1 = (u16*)mac1->data;
    u16* p2 = (u16*)mac2->data;
    for( n=0; n<3; ++n ) {
        if( *p1 != *p2 ) return (s16)*p1 - (s16)*p2;
    }
    return(0);
}

Assume nothing, and copy to word aligned storage, but the only reason for typecasting here is to satisfy the interviewer,

typedef unsigned short u16;
typedef   signed short s16;

int
MACcmp(MAC* mac1, MAC* mac2)
{
    if(!mac1 || !mac2) return(-1); //check for NULL args
    u16 m1[3]; u16 p2[3];
    memcpy(m1,mac1->data,6);
    memcpy(m2,mac2->data,6);
    for( n=0; n<3; ++n ) {
        if( m1[n] != m2[n] ) return (s16)m1[n] - (s16)m2[n];
    }
    return(0);
}

Save yourself lots of work,

int
MACcmp(MAC* mac1, MAC* mac2)
{
    if(!mac1 || !mac2) return(-1);
    return memcmp(mac1->data,mac2->data,6);
}
Community
  • 1
  • 1
ChuckCottrill
  • 4,360
  • 2
  • 24
  • 42
0

Function memcmp will eventually do the loop itself. So by using it, you would basically just make things less efficient (due to the additional function-call).

Here is an optional solution:

typedef struct
{
    int x;
    short y;
}
MacAddr;

int isEqual(MAC* addr1, MAC* addr2)
{
    return *(MacAddr*)addr1 == *(MacAddr*)addr2;
}

The compiler will most likely convert this code into two comparisons, since the MacAddr structure contains two fields.

Cavity: unless your CPU supports unaligned load/store operations, addr1 and addr2 must be aligned to 4 bytes (i.e., they must be located in addresses that are divisible by 4). Otherwise, a memory access violation will most likely occur when the function is executed.

You may divide the structure into 3 fields of 2 bytes each, or 6 fields of 1 byte each (reducing the alignment restriction to 2 or 1 respectively). But bare in mind that a single comparison in your source code is not necessarily a single comparison in the executable image (i.e., during runtime).

BTW, unaligned load/store operations by themselves may add runtime latency, if they require more "nops" in the CPU pipeline. This is really a matter of CPU architecture, which I doubt they meant to "dig into" that far in your job interview. However, in order to assert that the compiled code does not contain such operations (if indeed they are "expensive"), you could ensure that the variables are always aligned to 8 bytes AND add a #pragma (compiler directive) telling the compiler "not to worry about this".

barak manos
  • 29,648
  • 10
  • 62
  • 114
  • "Function memcmp will eventually do the loop itself. So by using it, you would basically just make things less efficient (due to the additional function-call)." - not necessarily. In fact, that's very unlikely. Stdlib functions do all sort of clever optimizations, not to mention compiler intrinsic functions which are not "called" but inline code is emitted for them. –  Dec 31 '13 at 21:35
  • 2
    How are you comparing.`long long` There is no way to tell if the last 2 unmapped bytes will be equal when the first six are. There is not even a guarentee that they are accessible. – Glenn Teitelbaum Dec 31 '13 at 21:50
  • @Glenn Teitelbaum, thanks for the correction, I had that in mind and somehow forgot to relate to that. Will fix the answer. – barak manos Dec 31 '13 at 21:54
  • I'm certain **C** does not define an `int` to be 4 `char` and neither `short` to be 2 `char`. Is not the `2nd isEqual()` approach highly dependent on that assumption? Presently work with embedded processors all the time that have sizeof(int) as 2 and work with network communication. If anything, `typedef struct { int32_t x; int16 y; } MacAddr;` would be better. – chux - Reinstate Monica Dec 31 '13 at 22:00
  • Also you can't propose 8 byte alignment, looking at an array of MAC. Odd elements will rarely be 8 byte aligned, but you should be able to compare them. – Glenn Teitelbaum Dec 31 '13 at 22:02
  • @chux, hi. Network communication will pose an additional problem here, of big-endian vs. little-endian, but only if you actually relate to the contents of the variables. A comparison should work fine, as both variables will be interpreted using the same endian-ness. As to the size definition of 'int' and 'short' - generally you are correct. 'int' can still be 2 bytes on some compilers. So for a generic solution, I suppose that the structure above should be properly "encapsulated with ifdef". – barak manos Dec 31 '13 at 22:08
0

May be he had in mind a definition of MAC that used unsigned char and was thinking to:

int isEqual(MAC* addr1, MAC* addr2) { return strncmp((*addr1).data,(*addr2).data,6)==0; }

which implies a cast from (unsigned char *) to (char *). Anyway bad question.

user1708042
  • 1,740
  • 17
  • 20
0

By the way, for those truly looking for a performant answer, the following is branchless, and while it does more fetches (one per char), they should all be from the same cache line, so not very expensive.

int isEqual(MAC* addr1, MAC* addr2)
{
    return
      (addr1->data[0] == addr2->data[0])
    & (addr1->data[1] == addr2->data[1])
    & (addr1->data[2] == addr2->data[2])
    & (addr1->data[3] == addr2->data[3])
    & (addr1->data[4] == addr2->data[4])
    & (addr1->data[5] == addr2->data[5])
    ;
}

See it live (and branchless) here

Glenn Teitelbaum
  • 10,108
  • 3
  • 36
  • 80