DEV Community

Discussion on: How can you swap two variables without using a third?

Collapse
 
cathodion profile image
Dustin King • Edited

To be a little bit sneaky, use part of the function itself as swap space. This would only work if that space could be after the return instruction.

In pseudo-C:

#define NOP {32 bits of assembly NOP instructions};

void swap(int* a, int* b){

    *&yep = *a;
    *a = *b;
    *b = *&yep;

    return;

    yep:
    NOP;
}

This isn't thread-safe though, and a decent operating system might throw exceptions if you try to have executable code modify itself.

Collapse
 
theoutlander profile image
Nick Karnik

It creates more memory though.

Collapse
 
zhu48 profile image
Zuodian Hu

The NOPs don't actually give you any memory. Those NOPs are wherever the executable image was loaded in memory, and the variable yep is on the stack. Assuming your standard C memory model.

Thread Thread
 
theoutlander profile image
Nick Karnik

I misread the post on the phone, but I see what the code is doing. Although, I'm not sure what assigning to NOP does?

Thread Thread
 
cathodion profile image
Dustin King

C memory layout:

C memory layout (source)

The function code itself is in the text segment. The variables for a particular invocation of the function are on the stack. Padding out the function with NOP creates space within the function, which I'm using as a variable. Basically I'm interpreting the "working memory" part of the post to mean "variables allocated on the stack". Now that I think of it, what I'm doing is basically a static variable, which (according to the link) C puts in the initialized data segment if you do it the right way, but then it would legitimately be a variable so I'd lose.

It's probably not a legit way to do things (and might be impossible if the text segment is read-only as the link says it might be), but people had already posted the legit ways.

Thread Thread
 
theoutlander profile image
Nick Karnik

Thanks for that explanation. It's been a while since I've written C/C++, but this approach makes sense. I love the thought process of cleverly using that available memory, even if it doesn't work out. 👏👏👏

Collapse
 
zhu48 profile image
Zuodian Hu

The variable yep is declared within a function body without a static qualifier, which means it's what the C standard calls an automatic storage duration variable. This means its duration is between the curly braces, and most compilers will use a register or put it on the stack.

Being completely nitpicky here, but the variable yep is declared after its use and also without a type. I'm sure modern compilers wouldn't even let you do that.

Modern operating systems load the text segment into a virtual memory page marked as read-only. So yes, even if this compiles, it will generate a segfault on modern operating systems.

Thread Thread
 
cathodion profile image
Dustin King

yep isn't a variable, though, it's a label, representing an offset from the start of the function.

I agree compilers and OS's will tend to prevent this. I said as much before, and trying to create a proof of concept in assembly has born that out.

It wasn't a completely fruitless exercise though, as it was a chance to learn some assembly, which provided some insights about the challenge that I might make a post about. Basically, swapping using math might not actually be more memory-efficient (however you define that, and without the kind of cheating I've been talking about) than swapping using "a variable".