11 ms·
The microcode and hardware in the 8086 processor that perform string operations
- kens 4y agoAuthor here for all your 8086 questions :-)
- pwg 4y agoKen, one tiny update. You have "a 4-megabyte (20-bit) address space" near the top of your post. 2^20 is a 1 Megabyte (in base-2 'megabytes') not a 4 megabytes address space.
- kens 4y agoI got it fixed just before your comment :-)
- benlivengood 4y agoDo you still write 8086 assembly for fun? I grew up with DOS, a86, and nasm and remember those times fondly. Once I had flat mode in Linux I never really looked back, and once I had x86_64 I never looked back, and now I rarely even delve below the interpreted/compiled level unfortunately. x86 had a closeness to the hardware that was fun to play with.
- kens 4y agoStrangely enough, I haven't written 8086 assembly since 1988, when I wrote the ellipse-drawing code used in Windows.
- garganzol 4y agoPardon my interest, are you happen to be a former Microsoftee?
- kens 4y agoI was an intern in the summer of 1988. Instead of staying, I went back to grad school which in retrospect probably cost me a fortune :-)
- madmoose 4y agoAaron Giles was just lamenting the other day that the GDI ellipse drawing is apparently slightly lopsided, since he's trying to recreate it :) https://corteximplant.com/@aaronsgiles/110121906721852861 https://corteximplant.com/@aaronsgiles/110121906721852861
- kens 4y agoHopefully that's not my bug :-) Before my code [1], small ellipses looked terrible: a small circle looked like a stop sign and others looked corrugated. [1] I can't take much credit. The code was Bresenham's algorithm, as explained to me by the OS/2 group. At the time, OS/2 was the cool operating system that was the wave of the future and Windows was this obscure operating system that nobody cared about. The impression I got was that the OS/2 people didn't really want to waste their time talking to us.
- myself248 4y agoIt's always boggled my mind that they'd have 32 bits of addressing registers, but overlap 12 bits, leaving just 20 useful bits. What a waste. I guess the segment:offset scheme had some advantages, but honestly, I've never felt like I had a good understanding of them. But, what if the overlap had been just 10 bits, or just 8, leaving a much larger functional address range before we got clobbered by the 20-bit limit; what if it was 22 or 24 bits of useful range? Can you speculate what effect such a decision would've had, and why it wasn't taken at the time? I understand in 1978 even 20 bits was a lot, but was that optimal?
- pwg 4y agoThe 20 bits of address was likely a direct result of Intel's decision to package the 8086 in a 40-pin package. They already multiplex the 16-bit data bus on top of 16 of the 20 pins of the address bus. But with only 40 pins, that 20-bit address bus was already using half of the total chip pinout. And, at the time the 8086 was being designed (circa. 1976-1978) with other microprocessors of the time having 16-bit or smaller address buses, the jump to 1M of possible total address space was likely seen as huge. We look back now, comfortable with 12+GB of RAM as a common size, and see 1M as small. But when your common size is 16-64k, having 1M as a possibility would likely seem huge.
- dfox 4y agoIt was not that much of an engineering decision as a simple requirement for the chip to be feasible. At that time 40pin DIL was effectively the largest package that could be made at production scale.
- kens 4y agoIntel's decision to use a 40-pin chip was mainly because Intel had a weird drive for small integrated circuits. The Texas Instruments TMS9900 (1976) used a 64-pin package for instance, as did the Motorola 68000 (1979). For the longest time, Intel was fixated on 16-pin chips, which is why the Intel 4004 processor was crammed into a 16-pin package. The 8008 designers were lucky that they were allowed 18 pins. The Oral History of Federico Faggin [1] describes how 16-pin packages were a completely silly requirement, but the "God-given 16 pins" was like a religion at Intel. He hated this requirement because it was throwing away performance. When Intel was forced to 18 pins by the 1103 memory chip, it "was like the sky had dropped from heaven" and he had "never seen so many long faces at Intel." [1] pages 55-56 of http://archive.computerhistory.org/resources/text/Oral_History/Faggin_Federico/Faggin_Federico_1_2_3.oral_history.2004.102658025.pdf http://archive.computerhistory.org/resources/text/Oral_Histo...
- mysterydip 4y agoIs there a performance advantage to using a microcoded instruction vice explicitly calling each instruction? Or is it a space/bugs-while-coding savings?
- rep_lodsb 4y agoA non-repeated string opcode is one byte for the CPU to fetch vs. several for the corresponding "RISC-like" series of operations (load, increment SI, store/compare, increment DI). With the REP prefix (another single byte), an entire loop could run in microcode without any additional instruction fetches. Remember that each memory access took 4 clock cycles and there was no cache yet. -- Eliminating opcode fetches might still speed things up today in some situations, but modern x86 cores are optimized to decode and dispatch several simple operations each cycle without having to go through a microcode ROM (and thus have to use a slower path for the complex instructions). Also the fact that compilers didn't emit most of the more complex/specialized instructions led to Intel not spending much effort on optimizing those.
- userbinator 4y agoAlso the fact that compilers didn't emit most of the more complex/specialized instructions led to Intel not spending much effort on optimizing those. I believe some compilers will still emit rep movs for memcpy, rep stos for memset, rep cmps for memcmp, and sometimes even rep scas for memchr/strlen if given the appropriate options.
- bell-cot 4y agoDirectly implementing many & complex instructions in silicon is fast, but takes a lot of transistors. Microcode running on a much simpler "actual" processor is slower, but requires far fewer transistors. IIR, ~all substantial CPU's of the past ~40 years have mixed the two approaches. (Microcode also makes it possible to design in bug-patching features. Possibly including patches for bugs in your direct-implemented instructions.)
- bonzini 4y agoIn the SCAS/CMPS annotated microcode, the path with the R DS microinstruction is for CMPS, not SCAS. SCAS compares AX against [ES:DI] while CMPS compares [DS:SI] against [ES:DI], so the paragraph before is slightly incorrect (should be "SCAS compares against the character in the accumulator, while CMPS reads the comparison character from SI").
- kens 4y agoThanks, I've fixed the post.
- mikepurvis 4y agoIt still boggles my mind that processors in the 1970s already had microcode— obviously it was vastly simpler and not doing the crazy branch prediction, speculative execution, and operation reordering that modern processors do, but it's still amazing to me that this architecture was there at all.
- pwg 4y agoMicrocode (the concept) is very much older than the 1970's. Per Wikipedia ([1]) the earliest system with something like 'microcode' dates back to 1947. What is 'special' for the 8086 is that this was a low cost microprocessor using microcode, as opposed to a multi-million dollar mainframe CPU. [1] https://en.wikipedia.org/wiki/Microcode#History https://en.wikipedia.org/wiki/Microcode#History edit: fix typo
- kens 4y agoYou mean the 8086, not the 8-bit 8080, right? The 8080 wasn't microcoded.
- pwg 4y agoIndeed, that was a typo. Fixed now. Thanks.
- plesner 4y agoBabbage's analytical engine used a form of microcode ~100 years earlier. Complex operations such as multiplication and division were implemented by lower-level instructions encoded as a series of pegs on a rotating barrel. Each micro-instruction ("vertical" in Babbage's terminology) could take several seconds to execute so a complete multiplication or division would take minutes.
- mikepurvis 4y agoThanks for that link! The concept of "Directly Executable High Level Language" is also kind of fascinating— seems almost like an early pitch for something like a native LISP or Java machine.
- bell-cot 4y ago> to create a 4-megabyte (20-bit) address space consisting of 64K segments sed "s/4-/1-/", perhaps?
- kens 4y agoOops, thanks.
- userbinator 4y agoThe 8086/88 does have an effective 4MB address space since it outputs the segment register in use during bus cycles, and I believe one of the official manuals did show that possibility, but I don't know of any systems that used such a configuration.
- anyfoo 4y agoToday I learned. I in my mind briefly went through anything that would foil such a plan, but with no caches whatsoever... should indeed have worked, even if it's weird (and deeply incompatible with what PCs did, of course). The only thing that comes to mind is fetching vectors from the IDT. I guess it simply output CS in those cycles?
- PaulHoule 4y agoOnce you got a pipelined architecture that stored instructions in a cache you could write a loop in assembly language that runs as fast as one of those string instructions, but if you didn't have that you'd be wasting most of the bandwidth to the RAM loading instructions instead of loading and storing data.
- jecel 4y agoThe 286 added "in string" and "out string" instructions. It turned out that if peripherals had a small internal buffer it was more efficient to use these new instructions instead of using DMA hardware. This is why hard disk controllers for the original PC and XT used DMA but from the AT on they normally didn't.
- rep_lodsb 4y agoIt was the 186 which added those. Wasn't widely used in PCs because it included some built-in peripherals that weren't compatible with the "standard" ones used by IBM in their original PC. And that standard PC's DMA controller was originally intended for use with the 8-bit 8080 (eighty-eighty, not eighty-eight) processor. It was slow and only supported 16 bit addresses. IBM added a latch that would store the high address bits, but they weren't incremented when the lower bits wrapped around. So buffers had to be allocated in a way that they didn't cross those boundaries, and the BIOS disk functions would return an error if your code didn't do this properly.
- anyfoo 4y agoI grew up with a "Siemens PC-D", 80186 and not fully IBM compatible for the reasons you said. However, it seems that the folks at Siemens were very enthusiastic about it, and ported a lot of software that accessed the hardware more directly, including most Microsoft software (Windows, Word, the C compiler...) and GEM. The BIOS was actually on disk, so updatable, and the BIOS updates came with a README file from the PC-D team that again give me the impression that some at least really liked working on it. A marvelous machine. High resolution (if monochrome), Hercules-like graphics, for example. But the kicker was that it actually had an MMU[1], built from discrete logic chips, in order to run SINIX (a Xenix 8086 derivate, but with added MMU support among other things) and enjoy full memory protection. I reverse engineered that MMU, it's quite fun. Paging wasn't possible though. [1] Early on as a variant called "PC-X", but they apparently did away with the early board revisions, and all machines I've seen say "PC-D/PC-X" on the back, so they all have the MMU and can be both.
- adrian_b 4y ago80186 and 80286 have been launched simultaneously in February 1982, so you cannot say that one of them has introduced INS and OUTS before the other. Nevertheless, due to their high cost for those times none of these 2 CPUs had seen much use before two years and a half later, when IBM launched the IBM PC/AT in August 1984. Most programmers have encountered INS and OUTS for the first time while using PC/AT clones with 80286. Embedded computers with 80186 became common only some years later, when the price of 80186 dropped a lot.
- userbinator 4y agoThe solution is that a string instruction can be interrupted in the middle of the instruction, unlike most instructions. This is true even for later x86 processors that move entire cachelines at a time, and also leads to one sneaky technique for detection of VMs or being debugged/emulated: https://repzret.org/p/rep-prefix-and-detecting-valgrind/ https://repzret.org/p/rep-prefix-and-detecting-valgrind/ https://silviocesare.wordpress.com/2009/02/02/anti-debugging-prefetch-tricks-and-single-stepping-through-a-rep-stosmovs/ https://silviocesare.wordpress.com/2009/02/02/anti-debugging...
- rep_lodsb 4y agoSmall nitpick: the REP STOSB isn't left in the prefetch queue while it's being executed by the microcode engine. The queue always contains the next instructions to execute (obviously it's not as simple for out-of-order architectures). The following should load AL with 0 on an 8088, 1 on an 8086: mov bx,test_instr+1 mov byte [bx],1 ;make sure immediate operand is set to one mov cl,255 ;max shift count to give time for prefetch cli ;no interrupts allowed align 2 shl byte [bx],cl ;clears byte at [bx] after wasting lots of time nop ;first byte in queue nop ;2nd nop ;3rd sti ;4th (intr. recognized after next instruction) test_instr: mov al,0ffh ;opcode is 5th, operand is 6th The 255x left shift is done in an internal register, during which the 8086 has more than enough time to fetch all six following bytes. I didn't test this code but am 99% certain it works.
- secondcoming 4y agousername checks out!
- saagarjha 4y agoI’m curious what rep lodsb even does lol
- 4y ago
- anyfoo 4y ago> Finally, the address adder increments and decrements the index registers used for block operations. It's kind of surprising to me that it's the address adder that increments/decrements the index registers. Since it's a direct operation on a register, naïvely I would have assumed it's the ALU doing that. Is it busy during that time? EDIT: Having read a bit further, I guess it's because of the microcode's simplicity... so, with the microcode being as it is, using the BL flag to instruct the logic to use the address adder to increment/decrement the index register prevents needing additional ALU uops, which would make the instructions slower? So then I guess it would not have worked to make that BL flag instruct the ALU instead? Does anyone know any details?
- kens 4y agoI think the motivation is that the address adder already has the capability to increment/decrement registers by various constants: incrementing the PC, incrementing the address for an unaligned word access, correcting the PC from the queue size, etc. If you updated the SI/DI registers through the ALU, you'd need a separate mechanism to get the constants into the ALU, as well as controlling the ALU to do this. But using the address adder gets this functionality almost for free.
- anyfoo 4y ago> SI → IND R DS,BL 1: Read byte/word from SI > IND → SI JMPS X0 8 test instruction bit 3: jump if LODS > DI → IND W DA,BL MOVS path: write to DI Is "W DA,BL" a typo, should it be "W DS,BL"?
- rep_lodsb 4y agoDA = "Data segment Alternate", or something like that. It refers to the segment register normally called ES, which string instruction implicitly use as destination (source being DS unless overridden). The names are those used in a patent filed by Intel and come from before the official documentation for the 8086 was written. It might make the microcode a bit more readable to invent a different notation that is more in line with normal x86 assembly, but then again this is a very niche topic :)
- anyfoo 4y agoAh, I forgot that it's DS:SI to ES:DI. Thanks.
- kens 4y agoNot a typo, but something I should clean up. The move instruction moves from DS:SI to ES:DI. The 8086 registers originally had different names (which is why AX, BX, CX, DX aren't in order) and the "Extra Segment" was the "Alternate Segment". So the 8086 patent uses "DA" to indicate what is now ES. ("A" for Alternate but I'm not sure why "D" is used for all the segments.) The register names were cleaned up before the 8086 was released. Andrew Jenner's microcode disassembly used the original names. I've been changing the register names to the modern names, but missed that one. So it should probably be "W ES,BL", although I don't really like "BL" either. (Maybe "PM" would make more sense for plus/minus?) A bit more on the original register names. The original 8080-inspired registers XA, BC, DE, HL were renamed to AX, CX, DX, BX. The original registers MP, IJ, IK were renamed to BP, SI, DI.
- anyfoo 4y agoI forgot that it moves from DS:SI to ES:DI, but that's actually super interesting that the registers were named differently originally (and I did notice that the AX/BX/CX/DX order is weird before)... What were CS and SS called? DC and DS?
- ataylor284_ 4y agoThese 8086 instructions were pretty cool coming from a 6502 background. The usual way to copy a block of memory in 6502 was something like this: ldy #len loop: lda source-1,y ; memory accesses: loads opcode, address, value sta dest-1,y ; memory accesses: loads opcode, address, stores value dey ; memory accesses: loads opcode bne loop ; memory accesses: loads opcode, offset So 4 instructions and a minimum of 9 memory accesses per byte copied, more if not in the zero page. Even unrolling the loop gets you down to 6. Compare this to the 8086: mov cx, len mov si, source mov di, dest rep movsb ; memory accesses: read the opcodes, then 1 load and 1 store per byte Even forgetting about word moves, you're down to 2 memory accesses per byte. No instruction opcode or branching overhead.
- kabdib 4y agoDon't forget the direction bit in the 8086's status register. [Don't forget the decimal mode bit in the 6502's status register :-)]
- chrononaut 4y agoWhat's noteworthy about the decimal mode bit in OP's example? (Not familiar with 6502 nuances, so this sounds interesting.)
- ataylor284_ 4y agoThey're both called the "D" flag, and they both globally control the behavior of certain processor instructions. Besides that, they're totally different. The 8086 D flag is the direction for string instructions, whether to increment or decrement the index registers after each repetition. One use was for moving memory between overlapping regions by starting at the end and working backwards. The 6502 D flag is for decimal mode. When set, the instructions ADC and SBC do BCD arithmetic instead of binary, e.g. 0x09 + 0x01 = 0x10 instead of 0x0A as you'd expect. The 8086 also has support for BCD, but took a different approach, using separate instructions DAA/DAS for the same purpose. Both can lead to bugs when you assume the flag is in the "normal" state but it somehow got flipped.
- elzbardico 4y agoString Operations! Amazing. Putting the emphasis on “Complex” in CISC.
- userbinator 4y agoARM, which is decidedly considered RISC, has STM/LDM. It also uses microcode and Ken has not surprisingly written about it too: http://www.righto.com/2016/02/reverse-engineering-arm1-processors.html http://www.righto.com/2016/02/reverse-engineering-arm1-proce...
- monocasa 4y agoFWIW, there's a lot of people that consider ARM a hybrid RISC/CISC, among other reasons, because of the presence of LDM/STM. Yeah, it literally has RISC in the name, but the SuperFX is called RISC by it's creators as well, but it's about as far aawy as you can get. RISC was a buzzword to the point that it's still a bit muddled to this day 40 years later.