Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

That XOR Trick (2020)

florian.github.io

Post reply on HN
Print view View original

111–120 of 243 posts

Re: That XOR Trick (2020)

#111

Post by dragontamer »

shiftingleft wrote: post #97
dragontamer wrote: post #48

Earlier quoted context omitted.

I wouldn't say "nobody" wants to see the XOR-trick solution. Its just that those who DO care about it is asking about the general solution: Reed-Solomon codes, or maybe a more modern (harder to understand) variant: like LDPC or Tornado codes. Anyone who needs to recover *ONE* symbol from a data-stream with noise actually needs to recover two, three... four... symbols in the general case. One symbol of erasure recover…

I don't see how the problem corresponds to erasure coding. Typically in erasure coding you know the locations of the erasures. Here, you don't know the location. Maybe you can elaborate on how it relates to erasure coding?

Since you asked this question in two different locations, I'll give a 2nd answer here.

One way to construct a Reed Solomon code is to create a Vandemonde Matrix.

    1 a^1 a^2 a^3 a^4 a^5 ...
    1 a^2 a^4 a^6 a^8 a^10 ...
    1 a^3 a^6 a^9 a^12 a^15 ...
    ...
All of the "1" values are from a^0.

As long as a^1, a^2, a^3... are distinct, then this matrix is invertible (aka: all rows / columns are linearly independent). In a GF(2^8) field, there are 2^8-1 distinct values (the values 0x01 through 0xFF), making a 255x255 matrix. The polynomial "x" (aka: 0x02) is often chosen to be the value of "a", but it can be any primitive element that loops around all 255 non-zero numbers and still work.

This Vandemonde Matrix has a very simple construction, but it is non-systematic (the data is "mangled" in encoded form, so we need to invert the matrix to decode). However, this non-systematic form is easier to see some patterns. Now lets take the 1st column:

    1
    1
    1
    1
    1
    ...
Hmmm... look familiar? What happens when we multiply the data vector with this column?? It becomes a bit more obvious:

                       1
                       1
                       1
    [d0 d1 d2 d3...] * 1
                       1
                       1
                       1
                       1
                       1
Remember, in Reed-Solomon, you perform operations over GF(2^blah). So all multiplications are GF-multiplications. But these are all multiplications by 1, so we can just ignore the complications of GF-multiplication entirely. (Even in GF(): a multiplication by 1 is just the identity).

To finish the matrix-multiply, we add everything together. But we do GF-addition (not regular addition). A GF-addition is also known as XOR. So the ultimate answer is:

    d0 XOR d1 XOR d2 ...
Which so happens to be the first parity bit of the non-systematic Reed Solomon code. As such, we've proven the relationship between the "XOR trick" and Reed Solomon (Vandemonde construction).

------------

The hamming-distance between codes is 1. We can correct floor(1/2) errors (aka 0 errors) and 1 erasure. As such, this "all 1s matrix" is a 1-erasure punctured Reed Solomon code.

Re: That XOR Trick (2020)

#112

Post by Thorham »

alowe wrote: post #104
Thorham wrote: post #96

Earlier quoted context omitted.

You're wrong. Remember that XOR works on individual bits. If what you're saying was true, then swapping bits that are both set to 1 would also fail, which means this algorithm wouldn't work at all. Edit: Ignore this post, I misread the original post as saying swapping the same values would fail.

They're not saying swapping equal valued variables breaks it. It's when the pointer is the same, using the trick to swap a variable with itself will set the variable to 0.

Yeah, I miss-read that. Thanks for pointing that out!

Re: That XOR Trick (2020)

#113

Post by danpalmer »

nickelpro wrote: post #19
danpalmer wrote: post #4

As mentioned in this article, x ^ x == 0. Fun fact, this is frequently used by compilers as a "cheap" way to zero out a register. In addition, there are comparatively few cases in programming where we XOR. Sure, it happens in things like games quite a lot, but the main use is actually _cryptography_. Between these two facts (more like hints really), I managed to reverse engineer the bulk of a piece of malware I was g…

Xor'ing registers isn't a compiler trick or arcane piece of lore, it's the canonical way to zero a register on most architectures. It's the only universally recommended way for both Intel and AMD x86 and x64 processors.

Thanks! Learning even more!

Re: That XOR Trick (2020)

#114

Post by [deleted] »

bidirectional wrote: post #108
whatshisface wrote: post #88

Earlier quoted context omitted.

Nobody complains about puzzles in tech interviews. People care about uncreative "did you read this book about interview questions" questions. If you want to test tech knowledge in tech interviews, ask a question that isn't in any book. That takes a lot more skill as an interviewer to pull off, but if you're a hiring manager, surely you can find someone on your team qualified to design a puzzle.

Google's policy is to extensively discuss interview questions internally, and blacklist any that are leaked. They are still complained about near-constantly on any tangentially related HN thread.

[deleted]

Re: That XOR Trick (2020)

#116

Post by wongarsu »

azhenley wrote: post #100
simias wrote: post #46

Careful abusing these tricks. Over 10 years ago I decided to implement an RC4 (arcfour) cypher to generate pseudorandom noise for a test program. The algorithm looks like (from wikipedia): i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile Being a smartass 1337 coder (and declaring intermediate variables alway…

The code from the Wikipedia article for XOR swapping [1] checks if the values are equal. void XorSwap(int *x, int *y) { if (x != y) { *x ^= *y; *y ^= *x; *x ^= *y; } } [1] https://en.wikipedia.org/wiki/XOR_swap_algorithm

At that point it's probably almost always better to just use some temporary space, rather than dealing with all the overhead of a branch (what if it's mispredicted, what about the resources in the branch predictor tied up by this that might cause something else to be mispredicted).

On the other hand there are many situations where you can guarantee that x and y are not the same space in memory (for example because they are local variables). There this trick might still be interesting (for the compiler or assembly programmer)

Re: That XOR Trick (2020)

#117

Post by shiftingleft »

dragontamer wrote: post #103
shiftingleft wrote: post #92

Earlier quoted context omitted.

I think in erasure coding you typically know the locations of the erasures: If a disk fails, you know which one failed. However, I don't see how you would know the locations in this problem? Maybe you can elaborate on how this problem relates to erasure coding?

Bingo, you're correct. > However, I don't see how you would know the locations in this problem? Well, that's just from the blogpost itself: > Application 2: Finding the Missing Number > You are given an array A of n - 1 integers which are in the range between 1 and n. All numbers appear exactly once, except one number, which is missing. Find this missing number. We can "find the missing number", but we don't know whe…

Ah, do you mean that solving the problem described in the blog-post helps actually using erasure coding, since it requires knowing which parts are missing?

Re: That XOR Trick (2020)

#118

Post by wongarsu »

shiftingleft wrote: post #80
nickelpro wrote: post #52

Earlier quoted context omitted.

It's not overhead, it's about dependency breaking. 32-bit xors on a single register are universally recognized as a zeroing idiom, which means the CPU doesn't have to wait for the results of previous operations in order to set the value of the applicable register to zero. In modern CPUs zero'ing idioms aren't even executed, they only get as far as the register allocater. The register allocater will allocate a zero'd…

Could you share a source about register allocation describing optimizations such as the one you described?

You might find what you are looking for by googling "register renaming"

Re: That XOR Trick (2020)

#119

Post by dragontamer »

shiftingleft wrote: post #117
dragontamer wrote: post #103

Earlier quoted context omitted.

Bingo, you're correct. > However, I don't see how you would know the locations in this problem? Well, that's just from the blogpost itself: > Application 2: Finding the Missing Number > You are given an array A of n - 1 integers which are in the range between 1 and n. All numbers appear exactly once, except one number, which is missing. Find this missing number. We can "find the missing number", but we don't know whe…

Ah, do you mean that solving the problem described in the blog-post helps actually using erasure coding, since it requires knowing which parts are missing?

If I'm reading your post correctly... yes. I think you've got it.

Re: That XOR Trick (2020)

#120

Post by creeble »

Fun XOR trick: using it to move a cursor across the screen without having to keep a buffer of the contents under the cursor (and putting them back).

It didn't always look great, but if you were moving a full-screen crosshair around, it was sufficient. Especially on hardware that was slow to move buffers to and from ram.

Unfortunately, using this pure-math technique was also patented until 2007 [0], much to the surprise of my former employer in 1986. Cadtrak had collected from companies like IBM and NEC and made a nice business as a troll.

[0] https://patents.google.com/patent/US4197590B1/en

Post reply on HN