View Question
Q: What is a "barrel shift"? ( Answered ,   1 Comment )
 Question
 Subject: What is a "barrel shift"? Category: Computers > Software Asked by: xavier687-ga List Price: \$200.00 Posted: 15 Aug 2004 20:12 PDT Expires: 14 Sep 2004 20:12 PDT Question ID: 388350
 ```I need to know exactly what a "barrel shift" is and it's connection to a dataset. Also, does a "barrel shift" actually rotate data? I have seen this in connection with processors and databases and need this answered quickly and correctly.```
 ```Hi xavier687-ga, Data shifting is a required element of many key computer operations, from address generation to arithmetic functions. Shifting a single data bit one field at a time can be a slow process, however. This is where a barrel shifter comes in. A barrel shifter is a combinational logic device/circuit that can "shift or rotate a data word by any number of bits in a single operation." http://computing-dictionary.thefreedictionary.com/barrel%20shifter Basically, a barrel shifter works to shift data by incremental stages which avoids extra clocks to the register and reduces the time spent shifting or rotating data (the specified number of bits are moved/shifted/rotated the desired number of bit positions in a single clock cycle). A barrel shifter is commonly used in computer-intensive applications, such as Digital Signal Processing (DSP), and is useful for most applications that shift data left or right - a normal style for C programming code. Yes, a barrel shifter can be used to rotate data. Rotation (right) is similar to shifting in that it moves bits to the left. With rotation, however, bits which "fall off" the left side get tacked back on the right side as lower order bits, while in shifting the empty space in the lower order bits after shifting is filled with zeros. http://shay.ecn.purdue.edu/~ee495al/Labs/Lab2/prelab/x58.html "A barrel shifter is a combinational logic circuit with n data inputs, n data outputs, and a set of control inputs that specify how to shift the data between input and output. A barrel shifter that is part of a microprocessor CPU can typically specify the direction of shift (left or right), the type of shift (circular, arithmetic, or logical), and the amount of shift (typically 1 to n-1 bits, but sometimes 1 to n bits)." http://www.ddpp.com/DDPP3_mkt/c06samp1.pdf (good graphs and examples of a 16-bit barrel shifter) "A four -input barrel shifter has four data inputs, four data outputs and two control inputs that specify rotation by 0, 1, 2 or 3 positions. A simple approach would use four 4-input multiplexers, since each output can receive data from any input. This approach yields the best solution only if the select lines can be pipelined, and the 4-input multiplexer design described above is used. The combination barrel shifter can be implemented in one level of four CLBs...." http://direct.xilinx.com/bvdocs/appnotes/xapp026.pdf "The action of a barrel shifter can be emulated in software, but this takes valuable time probably not available in real-time video or audio applications. The hardware barrel shifter is becoming a popular feature on the latest MCUs [microcontrollers]." http://www.electronicproducts.com/ShowPage.asp?SECTION=3700&PRIMID=&FileName=sepmot1.sep2001 Here is an example of a 32-bit cascadable barrel shifter "designed for use in floating-point normalization, word pack/unpack, field extraction and similar applications": http://www.logicdevices.com/ps/obsolete/pdf/lsh32.pdf I hope this has satisfactorily answered your question. If you need something explained further, please let me know by posting a request for clarification. Regards, --inquisitivega``` Clarification of Answer by inquisitive-ga on 16 Aug 2004 06:22 PDT ```Hi xavier897-ga, Just wanted to add some further information on the use and history of the barrel shift algorithm and barrel shifter hardware: Introduction of the Barrel Shifter in the Pentium 386 "The world of home computers didn't really become interesting until late 1986 when Intel released its 3rd generation chip - the 80386, or simply the 386....Both chips [Motorola countered the Intel 386 with its 68030 chip] also introduced something known as a barrel shifter, a circuit in the chip which can shift or rotate any 32-bit number in one clock cycle. Something used often by many different machine language instructions." http://www.emulators.com/docs/pentium_1.htm Lack of Barrel Shifter in the Pentium 4 The removal of the barrel shifter from Intel's P4 design (the barrel shift algorithm is implemented in the code instead of in the hardware)is blamed by most for its slowness. "It so happens that these bit rotates are at the heart of the RC5 algorithm [a fast block cipher used in key expansion, encryption, and decryption], being executed hundreds of times for each key checked, and the poor cycle count for this instruction on the P4 renders it so slow at this algorithm." http://lists.distributed.net/pipermail/rc5/2003-September/040144.html "Again, as an example, the Athlon and K5 and Pentium-III benefit in RC5 work because they implimented a "barrel shifter" in hardware - RC5 relies a LOT on one particular instruction that uses that barrel shifter. The P4 suffers a LOT from having it's barrel shifter implimented in microcode, which makes that particular instruction a LOT slower." http://www.mersenneforum.org/archive/index.php/t-1317.html Barrel Shifter Patents Numeric Data Processor - U.S. Patent 4,338,675, Palmer, et al. (Intel Corporation) July 6, 1982 "The numeric processor also includes a programmable shifter capable of arbitrary numbers of bit and byte shifts in a single clock cycle." http://patft.uspto.gov/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=%2Fnetahtml%2Fsearch-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN%2F4338675 Patent for a Barrel shifter circuit having rotation function - U.S. Patent 5,155,698, Niimi, October 13, 1992 http://patft.uspto.gov/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=%2Fnetahtml%2Fsearch-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN%2F5155698 Patent for a Bi-Directional Barrel Shifter - U.S. Patent 5,465,223, Nishimura (inventor), November 7, 1995 http://patents.nimblewisdom.com/patent/5465223-Barrel-shifter Regards, --inquisitivega``` Request for Answer Clarification by xavier687-ga on 16 Aug 2004 16:41 PDT ```inquisitive-ga: If I provided you with some information about a patent application, would you be able to verify if my invention is different from a barrel shift so my patent would be granted? You seems to know much about this topic and I'm willing to pay more if you can help me out more. Please reply and I'll post the question. Just give me a time when you will be checking Google Answers so I can make sure you are the one answering the question. I won't be availble tomorrow 8/16 until after 9pm Easter Standard Time, so please see if I can post after then.``` Request for Answer Clarification by xavier687-ga on 16 Aug 2004 17:06 PDT ```In my last email to you I said I was going to be available after 9pm Eastern Standard Time on 8/16. The correct date is 8/17 when I will be available to post a more in depth question. Can you help? I tipped you \$100.00 on the last question and will do the same on the next being worth an additional \$200.00. Please respond as soon as possible. My time is running out.``` Clarification of Answer by inquisitive-ga on 16 Aug 2004 18:38 PDT ```Hi xavier687-ga, First of all, thank you so much for the wonderful feedback and the additional tip. That made my day! As for your question on the patent application, I can't promise to know the answer without seeing the question, but I promise to do my absolute best to see that I provide the answer you require. If, for some reason, I can't answer it properly, I will honestly tell you that as well. Yes, I will be available on 8/17 and will look for your question. You can post the question to my attention if you would like - just put "For inquisitive-ga" in the subject line and the other Google Answers researchers will leave the question for me to answer. Thanks again! --inquisitivega```
 xavier687-ga rated this answer: and gave an additional tip of: \$100.00 `Possibly the best thought out answer I have ever seen to a question.`
 ```http://www.cse.psu.edu/~lusebrin/spec.htm Project specifications for barrel shifter versus logarithmic shifters using a transmission gate mux, a full static mux, and a dynamic mux. http://www.princeton.edu/~wolf/modern-vlsi/Overheads/CHAP6-1/sld004.htm graphic```