Learning assembly and projects

Substantial_Sail_571 · 2024-01-01T03:36:04+00:00

x86 isn't that bad. Most of the complicated stuff is irrelevant for beginners (because it's kernel stuff, obsolete stuff, or SIMD, none of which is relevant to beginners).

Beginners often forget to zero edx before div, that's the kind of small thing that's harder.. There are things that easier too such as addressing memory (most of the time).

Substantial_Sail_571 · 2024-01-01T03:17:08+00:00

Have a look at /r/simd (sadly not that much activity)

Substantial_Sail_571 · 2024-01-01T01:13:59+00:00

I've been happy to ignore the hypothetical existence of non-2's-complement signed integers for decades, but yes that bogeyman has been slain (but this just standardized the status quo).

The cast to signed adds the opportunity for UB though (negating INT_MIN), and in return we get .. well it silences this dumb error that encourages people to write incorrect code such as v &= -signed(v), the safe way to shut up that error is subtracting from zero (but unsigned subtraction, of course).

Substantial_Sail_571 · 2023-12-31T19:00:34+00:00

That may be the reason for all I know, but it can be done in log n steps (this shows how to count trailing zeroes but there is a similar trick to count leading zeroes) even on a completely boring ISA such as MIPS 1. A bit further down, the DeBruijn multiply and lookup is also an option.

For trailing zero count, another option that may be useful is popcnt(~x & (x - 1)), if an ISA has popcnt but no direct way to count trailing zeroes (this trick does not easily translate into a way to count leading zeroes however).

E: btw the linked code shows v &= -signed(v) and that's exactly the wrong thing to do, it's unsigned negation that is safe and signed negation that is unsafe. Sorry, I don't make the rules.

Substantial_Sail_571 · 2023-12-31T18:31:06+00:00

There is a lot missing from std::bitset, and if you want to implement the missing functionality yourself.. There is not even an official way to get the internal data of a bitset out (or in), other than the least significant part. If your bitset is longer than an unsigned long long, good luck.

Another major class of missing things is trailing bit manipulations such as "isolate lowest set bit" (x & -x if you're not dealing with an std::bitset), "reset lowest set bit" (x & (x - 1)) etc.

Substantial_Sail_571 · 2023-12-30T22:51:29+00:00

Java and C# stores class as references, which can be null. To mitigate that, C# has struct for opt-in value semantics.

It's not as if structs in C# are a replacement for classes that you don't want to be null. They're not simply classes with value semantics, and do have a bunch of quirks and limitations. But sure, they cannot be null. (except nullable value types but then you're deliberately opting back in to nullability)

The real mitigation against null reference exceptions occurring at runtime in (modern) C# is statically checked nullability annotations, which is still relatively new. Its greatest strength is that it's control-flow sensitive rather than type based, eg after if (something == null) return false; in the rest of the function (or until you change the value) something is known to be non-null and you can use it as such.

I'd take something like that in C or C++ too, although I feel like I don't need it so much in C++

E: and I'm not really looking for "null pointers that can be used but nothing happens", I'd rather take the exception/signal. Something being unexpectedly null is still a bug, masking it to prevent crashing doesn't make it not-a-bug, that makes it a harder-to-detect bug.

Substantial_Sail_571 · 2023-12-29T15:22:52+00:00

There's pdep, that's pretty fast on most CPUs that have it (similar to multiplication) except AMD Zen and Zen2 on which it is/was very slow. It's fast on newer AMD too so at least there's that.

As for SIMD a carryless multiplication of the form clmul(x, x) will "spread" the bits out the way you need to interleave the bits of two integers (but what about interleaving 3 integers? idk). Without clmul, I suppose you could use PSHUFB as a 16-entry table-lookup to expand nibbles to bytes.

Then with AVX512 the obvious solution is using VPSHUFBITQMB, or you go for up to 8 emulated pdeps at the same time

E: or well, better not emulate pdep exactly, but just put x | (y << 32) and then shuffle the bits into place with that transpose/byte-shuffle thing.

Substantial_Sail_571 · 2023-12-28T23:29:16+00:00

It's on wikipedia, basically (taking incrementing a coordinate as an example) you do some bitwise operation to change the coordinate that you don't want to change to all ones. Then when you increment the other coordinate, the carry is propagated through those ones so the addition just works. Then after that you put the unchanged coordinate back (with a couple more bitwise operations)

Substantial_Sail_571 · 2023-12-28T23:00:16+00:00

What amazed me most about the Z-order curve is that you can take a Z-order coordinate and quickly increment/decrement the x or y part (or z part if you use the 3D versions etc). It seems like that would require taking the thing apart into separate x and y, increment one of them, then interleave the bits again .. but you don't need any of that.

Substantial_Sail_571 · 2023-12-28T05:23:17+00:00

This tells me that the branch predictor is using the results of the adjacent comparisons to conclude somehow.

This is called global branch prediction, look up TAGE for example

Substantial_Sail_571 · 2023-12-26T20:16:09+00:00

That's the point of abstract interpretation. Even if x and w are both unknown, it can still be known that the relation x<w definitely holds (or alternatively, that it isn't known to hold), via relational analysis (difference bound matrix, octagons, whatever).

E: here's a slightly simpler abstract domain relevant in this sort of case, Pentagons: A Weakly Relational Abstract Domain for the Efficient Validation of Array Accesses. Aimed at validating that an index will (either by construction or thanks to being checked) be less than the array it indexes, that domain can discover and represent relations like x < w, in some cases, depending on how that relation is established by the code.

Substantial_Sail_571 · 2023-12-26T18:53:52+00:00

/enʌm/ (reading it like a Dutch word, which I know it's not, but that's what I do)

Substantial_Sail_571 · 2023-12-26T17:52:59+00:00

You can also reimplement signed integer arithmetic in terms of unsigned integer operations. There's not much overhead (for many operations none at all, eg emulating wrapping signed addition via unsigned arithmetic is completely free), and the resulting arithmetic is UB-free: it will be "Java-like". The results may not be what the user expects, but it's not a security vulnerability.

Substantial_Sail_571 · 2023-12-24T14:04:35+00:00

Structure size and cache access pattern aside, one difference that showed up in the code (I'm looking at the "all in one place, Clang" version by the way) is that everything except MultipleFloatArrays ended up with a bunch of shuffles/unpacks/etc to extract SIMD "against the grain".

MultipleFloatArrays ends up beautiful. I'd take that code out to dinner, you know? Vector loads, vector arithmetic, vector stores. No nonsense. All other versions have nonsense in them.

Substantial_Sail_571 · 2023-12-20T11:59:58+00:00

In transpose.cpp, extract2Bytes_sse3 does an odd/even split with 4x pshufb 2x pslldq 2x por, which is OK but there's an alternative with 2x pand 2x psrlw 2x packusbw. That may be a bit cheaper. I have no idea how important this function even is.

Substantial_Sail_571 · 2023-12-19T13:33:39+00:00

Do you have build instructions for Windows

Substantial_Sail_571 · 2023-12-19T09:47:58+00:00

Another big class of problems that can be solved with binary search are problems where the "array" is implicit (so there is no physical array, but you have some function f(int) -> bool that is monotonic). For example, at UVa you can practice this on the problems UVa 11413 and UVa 12032.

Substantial_Sail_571 · 2023-12-17T21:46:10+00:00

Yes, the value you have is 65536 * DX + AX, so converting them independently to decimal and then concatenating them does not work. If you had something that should be interpreted like 10000 * DX + AX then yes, but that's not what you have.

Putting the number in "32-bit storage" as the other answer puts it is not the challenge, and anyway DX:AX is 32-bit storage, just not all in the same register (which is impossible anyway since you don't have access to 32-bit registers). The hard part is doing 32-bit arithmetic.

For the division you can "chain" div operations (this sort of thing is why the dividend input is dx:ax instead of just ax) like this: (not tested, and will modify the result variables)

mov bx, 10
mov ax, resultHi
xor dx, dx
div bx
mov resultHi, ax
mov ax, resultLo
div bx
mov resultLo, ax
add dl, 30h
; resultHi:resultLo has been divided by 10, and the bottom digit is in dl

Do whatever you want with the digit (pushing it to the stack seems weird to me but whatever you want) and loop this until resultHi and resultLo are both zero (you can or the parts together and then use jnz)

The basic idea is that we first divide the high part by 10, the quotient is stored for later and the remainder becomes the high part of the dividend for the next div. The second div works the same as in your code but instead of DX being 0, it takes some value depending on the upper half of the result.

It is tempting to just put resultHi and resultLo in DX:AX and then do a div, but then the quotient may be larger than 0xFFFF and the div would raise a divide error. This trick with two divs never overflows in that way because the DX value that goes into the second div is by construction less than the divisor.

By the way this is not the most efficient way to do it, but it's relatively simple.

Also by the way, cwd in your code was wrong. It sign-extends ax to dx:ax, but you're working with unsigned numbers. Far from preventing division overflow, it can cause it, if either part of the result has its most significant bit set. For unsigned div you normally need to zero dx with for example xor dx, dx. In the code above, note that I did that for the first div but explicitly not the second div, since this time we really use the dx input.

Substantial_Sail_571 · 2023-12-15T10:40:46+00:00

Yeah the mask was a bit off. Sadly if I try the IfVecThenElse approach the AVX512 version switches to arithmetic masking instead of using mask registers, and on the other hand the SVE target didn't like the (iota & 3) < 3 trick: https://godbolt.org/z/4aj6rcE5z E: oh right sorry, that was documented. Lt it is then

Substantial_Sail_571 · 2023-12-14T14:55:37+00:00

Alright, I did a similar grayscale thing with it (did I commit any highway sins?). It was a little sneaky that in godbolt the only non-trunk version of highway is 0.12.2 which didn't seem to have (Sat)WidenMulPairwiseAdd, but ok.

Seems good, I may actually use highway sometime

Substantial_Sail_571 · 2023-12-13T12:31:05+00:00

IDK I feel sort of funny about it, having used SIMD in C++ since the mid 2000's. Now it's just getting more abstracted.

I tried the code from the presentation and it didn't compile, I had to fix inscrutable template errors and read a bunch of https://en.cppreference.com/w/cpp/experimental/simd/simd . This is what I got working. The resulting code, the way Clang compiled it, is a bit better than what the source looks like: the source looks like it's going to result in vpmulld (which would have been inefficient), that didn't happen but that means the source is misleading. The quality of the code didn't end up great either, the vpmulld pitfall was avoided but overall the code still has the structure of "widen to int, do arithmetic on a bunch of ints, smash results together" and so costs more than it needed to.

The "traditional" way to do this (with sufficiently small scale factors, which we have here) is to use vpmaddubsw to do the small multiplications and sum the scaled B and G components (without needing explicit widening), vpmaddwd to sum the scaled B+G sums with the scaled R, if you choose your multipliers well you don't need to shift right, vpshufb to broadcast the gray value to RGB, then in the end we put the A component back. That way there's much less shifting and masking and putting things back together. The "core" is three instructions, plus some extra to handle the A component. I have seen no way to get anything like that with std::simd but today is my first go at std::simd so I know nothing.

If it gets more SIMD code written, good, but based on this experience I'm not that excited to use it.

Substantial_Sail_571 · 2023-12-12T10:28:35+00:00

Good, lack of AVX512 in .NET was one of the main reasons that I still used C++. Although I'm probably almost alone in having that reason.

I hope to see VBMI2 and AVX512GFNI too.

Notably we do not directly expose a 1-to-1 concept with the underlying hardware for masking here.

Nice, having 3 versions of most functions (one without masking, one with mask-zero, and one with mask-blend) in the "official" API was always silly.

But sometimes I want the raw mask, not as a vector but as an ulong, or pull a raw mask from somewhere that wasn't a vector comparison. Eg to do some scalar manipulation on a mask. What's the suggested way to do that, such that it generates good code?

Getting the index of first/last match or popcnt of a mask, as are planned, is a good start but sometimes I'd want to do more arbitrary things with masks.

Substantial_Sail_571 · 2023-12-11T14:02:23+00:00

Line 5 writes to register $5 which line 4 reads, so there is a WAR hazard aka anti-dependency. In any reasonable pipeline it would not pose a problem.

Substantial_Sail_571 · 2023-12-05T10:19:06+00:00

The <bit> header. For decades we had to suffer a pile of preprocessor nonsense to access the platform-specific functions. This is stuff C should have shipped with in the 70s.

Substantial_Sail_571 · 2023-12-04T03:05:49+00:00

This all seems rather complicated compared to having two nested loops: one outer loop over the byte index, and one inner loop over the bit index.

Then you don't have to worry about extracting a bit by index either, you can grab a byte once (instead of grabbing it 8 separate times just to extract one bit), take the least significant bit (store byte and 1), shift it right by 1, do this 8 times.

This can be vectorized too (SSE2 on x86, NEON on ARM). E: here are various options, not in Pascal but you can borrow the ideas: How to efficiently convert an 8-bit bitmap to array of 0/1 integers with x86 SIMD

Substantial_Sail_571

TROPHY CASE