I've encountered a gnarly problem repeatedly over many years. I don't have any immediate requirement for a solution on 6502 but it is likely that someone may require it sooner or later. Indeed, with a solution to hand, you may find immediate use for it.

The problem is a binary or bit matrix transpose. Starting with a square grid of 8*8 bits, flip the grid along one diagonal. Another explanation would be to take eight bytes of data and transform it such that all of the top bits are held in one byte, all of the next most significant bits are held in the next byte, all the way down to the least most significant bits from across the eight bytes grouped into the last byte. This problem occurs in numerous unrelated places. It occurs in audio and video compression. It was also used on the the Amiga port of Doom so that the chunky textures could be displayed on the planar video system of a 32 bit Amiga's AGA chipset. It can also be used to bit-bang synchronous serial streams. This could be for any purpose from MicroSD RAID, serial DACs to WS2812 digital RGB LEDs. There are related subproblems, such as 6*8 bit and 6*2 bit transpose, for example, to drive six 18 bit serial DACs.

There are places where bit transpose is not useful. For example, I thought that it would be a really great idea to save energy and incorporate an 8*8 bit transpose into a bit-banged, interrupt driven, eight port network switch. However, after realizing that it required a huge number of clock cycles every eight interrupts, I dropped it and used the simple method.

I have a good solution in C which is suitable for processor architectures with fairly symmetric registers. This is divided into separate cases for architectures with 64 bit registers (an absolute joy), 32 bit registers, 16 bit registers (should work really well on RCA1802 and TMS9900) and 8 bit registers. Unfortunately, it took me three days to get anything sane out of avr-gcc and I am concerned that any routine with, for example, char foo[7] will generate a huge amount of unnecessary 16 bit addition on 6502. C compilation on 65816 might be sane but I am not hopeful.

Starting with eight contiguous bytes in zero page, it is probably easiest to overwrite data. The dumbest technique to implement 8*8 binary transpose is 1-8 obtuse sequences of ROL zp instructions each ending with a fixup for the last bit. However, this requires more than 128 bytes, more than 256 clock cycles and moves everything through the carry bit. It is definitely possible to write a faster implementation. For 2^2N matrix bits (2^N along each side), it is possible to transpose in N steps. This is a fractal Battenberg cake. For 8*8 binary transpose, the first (or last) step is to swap only two opposite quadrants of 4*4 bits. This may or may not be aided with the six instruction nybble swap sequence. For 2*2 block swaps and 1*1 block swaps, shift operations should handle a minimum of four useful bits.

It may or may not be fastest to handle 4 bit, 2 bit and 1 bit left and right shift operations using LUTs [Look-Up Tables] because it allows masking and shifting to be handled in one step. Although it initially appears to require six pages of tables, left shifts only require 128, 64 and 16 table entries. It is possible for two of these tables to share one page by applying AND immediate or OR immediate to some table inputs while four bit left shift may be combined with nybble swap or implemented the hard way. This reduces tables to a maximum of four pages - and it may be possible to put the transpose algorithm in the 64 byte hole between the 128 and 64 entry tables.

Anyhow, if your solution requires more than 1KB or 256 clock cycles, there is definitely a smaller or faster solution. However, it is possible that the fastest solution exceeds 1.5KB.

_________________
Modules | Processors | Boards | Boxes | Beep, Beep! I'm a sheep!

I might benefit from this transposing method when printing non-proportional fonts to the graphics screen if it is quite a bit faster than the ROL method you mention.

Do you have any sample code?

Isn't it just something like this?

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

Opps small out by one error in the output area.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

There's a method that uses a bunch of 3-cycle EORs instead of a bunch of 5-cycle ROLs. I found the 32-bit C source, attributed to Henry S. Warren Jr., but I hesitate to post it here due to potential copyright issues. If I can successfully translate it to optimized 6502 assembly, I won't hestitate to post my version, but I'm having difficulty grokking the algorithm right now, and I have a bunch of other stuff on my plate. I won't be the least bit offended if someone else beats me to the punch.

Put:
t = (x ^ (x >> 7)) & 0x00AA00AA;
into your favorite search engine if you feel like giving it a go (it'll certainly be larger than Bitwise's 32-byte effort, and it's too early for me to tell if it has much chance of being any faster than 527 cycles).

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)

Firstly, I would have suggested a smaller problem if I knew the full scope of binary matrix transpose. Secondly, if you want something which will only be used occasionally and is easy to understand then use BitWise's implementation and don't look any further.



When I first encountered this problem, my inclination was to write the unrolled version of your implementation in MC68000. Your solution is, by far, the most concise, legible and easily maintained version that we are likely to see. Furthermore, it is ideally suited to be trimmed down for the subproblems. However, if all bits are passed through the carry flag then it is definitely not the fastest algorithm for the 8*8 case.



You've given me an idea for implemenation. It is possible to swap variables without using a temporary variable by using EOR swap. Many of the explanations for EOR swap are quite baffling. Therefore, I have drawn a Boolean diagram and truth table. This may or may not be helpful when satisfying yourself that EOR swap performs as expected. It may be useful to extend EOR swap to a bit matrix transpose by introducing bit masks, bit shifts and/or LUTs. (Apologies in advance for use of C notation. This directed at barrym95838 as pseudo-code for conversion into 6502 assembly.) The trivial EOR swap is:-



With nybble swap LUT, this would be:-



Unfortunately, this performs something slightly different to the desired algorithm. Specifically, this concurrently exchanges two variables while nybble swapping both variables. This can be adapted by using bit masks. One line of the 4*4 swap can be implemented as:-



where the LUT swaps pairs of 4 bits, the inner array index and logical operation may be implemented using AND zp,X and the outer array index and logical operation may be implemented using EOR abs,Y. It may be desirable to substitute lut4 with bit shift operations but it is probably faster to use LUTs for the 2*2 and 1*1 cases. This solution exceeds 512 bytes and may exceed 256 clock cycles. It is probably less than 2x faster than BitWise's solution yet more than 16x larger. Regardless, it provides an example of why compilers fail to produce sensible output. Unaless the compiler's input is phrased in a very specific manner - with fore-knowledge of the target architecture - the compiler cannot apply a sensible set of transformations and optimizations.



I suspect the seven bit shift is derived from Donald Knuth's re-occurring binary fraction technique. If so, I sympathize with your bafflement.

I tried the suggested search and found a similar question for PIC where someone suggested that it was a pointless codegolf exercise. Worse, many responded with Intel AVX512 "solutions". I also found a header in the FastLED library which is typically used to control WS2812 digital LEDs and similar devices which use incompatible serial formats. Anyhow, people are definitely running binary matrix transpose on 8 bit systems and people are definitely using it for practical tasks, such as light control.

_________________
Modules | Processors | Boards | Boxes | Beep, Beep! I'm a sheep!

I took a brief swipe at translating the C to 6502 assembly, but gave up after about 15 minutes, when it became obvious that the attempt couldn't match Bitwise for size or cycle count, no matter which way I tried to slice it.

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)

Good! I didn't think there was a faster way without creating huge tables, but still you made me doubt myself at writing effiecient code.

EOR swap is a failure.

becomes

and

becomes

There are a few opportunities to optimize but the half byte swap takes about 41 clock cycles. Four sets are required at three different scales. There are minor opportunities to optimize but it requires something like 768 bytes of LUT, 360 bytes of program and 492 clock cycles or a little less. It might be a marginal speed improvement compared to the binary fraction technique but it is likely to be far larger.



I was completely wrong about that. Despite the use of read-modify-write instructions and the possibility of dead cycles, passing all data through the carry flag and assembling rows of bits in the accumulator appears to be the fastest method by a wide margin. This is particularly true for smaller transpose operations. Assuming no dead cycles, BitWise's implementation requires 32 bytes and far less than 400 clock cycles.

With two extra instructions, it is possible to make BitWise's implementation perform two simultaneous matrix transpose operations. Specifically, the loop may begin with LDA <TRNS,x // ROL A and end with STA <TRNS,x // DEX. This disperses bits from one matrix while collating another. This doubles the efficiency of the rotate instructions and typically requires less than four clock cycles per bit transposed. The overhead of the tweaked algorithm is minimal to the extent that it may be preferable to only provide a double transpose operation. Even with this impediment, the tweaked algorithm is approximately three times faster than other suggestions and is a further demonstration of compiler inefficiency. This is especially true when an additional entry point allows simultaneous 8*X and X*8 transpose where X<=8.

_________________
Modules | Processors | Boards | Boxes | Beep, Beep! I'm a sheep!

This sounds good on paper but doesn't translate to code in some cases. It sounds like you are trying to use the Accumulator for both the DATA byte and the TRANSPOSE byte or transpose the horizontal and vertical axis in one pass. This might work if only transposing full bytes and not bits. This basically has a rotating square effect.

LDA DATA+0
STA TEMP
LDA DATA+8
STA DATA+0
LDA DATA+64
STA DATA+8
LDA DATA+56
STA DATA+64
LDA TEMP
STA DATA+56

Also comes to mind that speed may not be essential in some cases as once the data has been transposed, it can be saved as data that can take the place of the non-transposed data that is getting loaded each time and being transposed every time. Making proportional fonts out of bitmap fonts may fall in this category.

Rotating the graphics screen or window can be another use. But the question becomes, how wide is the pixel (in bits) if we want to preserve color?

Transposing 1-bit, 4-bits, 8-bits ..etc would require slight differences to the code.