ttl@sti.fi (Timo Lehtinen) (08/14/90)
This might be trivial, but here goes...
What's the most optimal way to reverse the bits in an unsigned char,
i.e. change from MSB to LSB ordering ?
ttl
--
____/ ___ ___/ / Kivihaantie 8 C 25
/ / / SF-00310 HELSINKI, Finland
____ / / / Phone: +358 0 573 161, +358 49 424 012
Stream Technologies Inc. Fax: +358 0 571 384pmk@craycos.com (Peter Klausler) (08/14/90)
If the range of your bit-reversal function is limited to chars, use a lookup table. If your range is bigger, split your data into bytes and then use a lookup.
kdq@demott.COM (Kevin D. Quitt) (08/14/90)
In article <1990Aug13.185757.3236@sti.fi> ttl@sti.fi (Timo Lehtinen) writes: >This might be trivial, but here goes... >What's the most optimal way to reverse the bits in an unsigned char, >i.e. change from MSB to LSB ordering ? > If by optimal, you mean fastest with the least code, try a char[256] array with the bits already reversed. You just look 'em up. (It may be gross, but the table+code is often smaller than the conversion code).
chris@genly.UUCP (Chris Hind Genly) (08/14/90)
>In article <487@demott.COM> kdq@demott.COM (Kevin D. Quitt) writes: >In article <1990Aug13.185757.3236@sti.fi> ttl@sti.fi (Timo Lehtinen) writes: >>This might be trivial, but here goes... >>What's the most optimal way to reverse the bits in an unsigned char, >>i.e. change from MSB to LSB ordering ? >> > If by optimal, you mean fastest with the least code, try a char[256] >array with the bits already reversed. You just look 'em up. (It may be >gross, but the table+code is often smaller than the conversion code). You'll need something to generate the table. Here is a small routine to do it. On a mini-super, where the alus are much faster than memory, this routine may actually be faster than a table lookup. For a pc, a table lookup is faster. /* * A bit reverse for 8 bits. */ unsigned char bitrev(i) unsigned char i; { i = (i & 0x0f) << 4 | (i & 0xf0) >> 4; i = (i & 0x33) << 2 | (i & 0xcc) >> 2; i = (i & 0x55) << 1 | (i & 0xaa) >> 1; return i; } * * * \|/ * _______ --O-- ____/ KC1VP \____ * /|\ * _____________/ (203) 389-8680 \_______________ ______/ 95 Fountain Terr., New Haven, CT, USA, 06515 \_______ / Chris Hind Genly chris@genly.uucp uunet!hsi!genly!chris \ ----------------------------------------------------------------
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (08/14/90)
In article <1990Aug13.185757.3236@sti.fi>, ttl@sti.fi (Timo Lehtinen) writes: > What's the most optimal [what a long-winded way of saying "best"] > way to reverse the bits in an unsigned char? Use a table. -- The taxonomy of Pleistocene equids is in a state of confusion.
gld2@clutx.clarkson.edu (E.W.D, ,0,0) (08/14/90)
From article <487@demott.COM>, by kdq@demott.COM (Kevin D. Quitt): > In article <1990Aug13.185757.3236@sti.fi> ttl@sti.fi (Timo Lehtinen) writes: >>This might be trivial, but here goes... >>What's the most optimal way to reverse the bits in an unsigned char, >>i.e. change from MSB to LSB ordering ? >> > If by optimal, you mean fastest with the least code, try a char[256] > array with the bits already reversed. You just look 'em up. (It may be > gross, but the table+code is often smaller than the conversion code). Didn't this go around a while back? Having actually tried tables we found that the best technique we found was to swap half words, then half half words, ... down to adjacent bits (at least on VAX, Sun 3, and a few others). This resulted in the most dramatic cooling of one of the hottest hot spots I've seen. long int n; /* the number */ long int numberofbitstostartwith; /* we're interested in this number of bits */ long int revn; /* the reversed number */ revn = n << ((sizeof (n) * 8) - numberofbitstostartwith); revn = (0x0000FFFF & (revn >> 16)) | (0xFFFF0000 & (revn << 16)); revn = (0x00FF00FF & (revn >> 8)) | (0xFF00FF00 & (revn << 8)); revn = (0x0F0F0F0F & (revn >> 4)) | (0xF0F0F0F0 & (revn << 4)); revn = (0x33333333 & (revn >> 2)) | (0xCCCCCCCC & (revn << 2)); revn = (0x55555555 & (revn >> 1)) | (0xAAAAAAAA & (revn << 1)); Eliot W. Dudley edudley@rodan.acs.syr.edu RD 1 Box 66 Cato, New York 13033 315 437 0215
dhoyt@vw.acs.umn.edu (08/14/90)
In article <1990Aug13.185757.3236@sti.fi>, ttl@sti.fi (Timo Lehtinen) writes... >This might be trivial, but here goes... >What's the most optimal way to reverse the bits in an unsigned char, >i.e. change from MSB to LSB ordering ? You don't have to change anything. Big and little endians only cause trouble when you look at different integer formats. Bytes is bytes, as they say. Everyone thinks that 2^128 is 10000000. The trouble arises with characters packed into integers. Everyone knows that in 'abcd' 'a' is the first character. But if packed into an integer on a dec, intel or national semi machine the string would read 'dcba.' That is the first letter, 'a', will be in the Least Significant BYTE. Most others would say the integer would look like 'abcd.' The first character is the Most Significant BYTE. The advantage to MSB over LSB is that a simple integer compare is also a simple character compare. The advantage of LSB is that the first character is always in bits 7:0 regardless of the word size; be it 8 bits, 16 bits, 32 bits or 64 bits. On a MSB it would be in 7:0 of an 8 bit integer, 15:8 for 16, 31:24 for 32 and 63:56 for a 64 bit integer. However, with MSB you have to take in account the natural word size to figure out just what bits 63:56 means on a 32 bit machine. Note that I started counting my bits at 0 which not all people like. But it makes my life much easier (the zero'th bit contains the 2^0 bit, the one'th bit the 2^1, and so on...). Most people shouldn't think about MSB/LSB too much. It has a tendency to hurt people's brains. If characters are always in char variables and integers always in integer variables and you never use unions, you shouldn't ever have problems. Except when you do binary ftp's or swap binary (not character!) data with machines on the wild side. david paul hoyt | dhoyt@vx.acs.umn.edu | dhoyt@umnacvx.bitnet
jacobs@cs.utah.edu (Steven R. Jacobs) (08/14/90)
In article <2059@ux.acs.umn.edu> dhoyt@vw.acs.umn.edu writes: > In article <1990Aug13.185757.3236@sti.fi>, ttl@sti.fi (Timo Lehtinen) writes... >>This might be trivial, but here goes... >>What's the most optimal way to reverse the bits in an unsigned char, >>i.e. change from MSB to LSB ordering ? > > You don't have to change anything. Big and little endians only cause > trouble when you look at different integer formats. Bytes is bytes, as they > say. Why do you assume this is a big/little endian question? Reversing bit order is a common operation used in DSP (digital signal processing) algorithms. -- Steve Jacobs ({bellcore,hplabs,uunet}!utah-cs!jacobs, jacobs@cs.utah.edu)
darcy@druid.uucp (D'Arcy J.M. Cain) (08/15/90)
In article <1990Aug13.222454.3862@craycos.com> pmk@craycos.com (Peter Klausler) writes: >If the range of your bit-reversal function is limited to chars, use a lookup >table. If your range is bigger, split your data into bytes and then use a >lookup. I believe the original poster meant that he wanted to change endian-ness. Something like: #define reverse_word(i) ((i | (i << 16) >> 8) & 0xffff) If you are worried about side effects a slightly less efficient way is: #define reverse_word(i) (((i * 65537L) >> 8) & 0xffff) -- D'Arcy J.M. Cain (darcy@druid) | D'Arcy Cain Consulting | MS-DOS: The Andrew Dice Clay West Hill, Ontario, Canada | of operating systems. + 416 281 6094 |
kdq@demott.COM (Kevin D. Quitt) (08/15/90)
In article <1990Aug14.124259.13475@sun.soe.clarkson.edu> gld2@clutx.clarkson.edu (E.W.D, ,0,0) writes: >From article <487@demott.COM>, by kdq@demott.COM (Kevin D. Quitt): >> In article <1990Aug13.185757.3236@sti.fi> ttl@sti.fi (Timo Lehtinen) writes: >>>This might be trivial, but here goes... >>>What's the most optimal way to reverse the bits in an unsigned char, ^^^^^^^^^^^^^ >>>i.e. change from MSB to LSB ordering ? >>> >> If by optimal, you mean fastest with the least code, try a char[256] >> array with the bits already reversed. You just look 'em up. (It may be >> gross, but the table+code is often smaller than the conversion code). > > >Didn't this go around a while back? > >Having actually tried tables we found that >the best technique we found was to swap half >words, then half half words, ... down to >adjacent bits (at least on VAX, Sun 3, and a >few others). This resulted in the most dramatic >cooling of one of the hottest hot spots I've seen. Very interesting, I'm sure, but what does this have to do with the original request? He wanted to know how to reverse a single byte. -- _ Kevin D. Quitt demott!kdq kdq@demott.com DeMott Electronics Co. 14707 Keswick St. Van Nuys, CA 91405-1266 VOICE (818) 988-4975 FAX (818) 997-1190 MODEM (818) 997-4496 PEP last 96.37% of all statistics are made up.
news@ism780c.isc.com (News system) (08/15/90)
In article <1990Aug13.222454.3862@craycos.com> pmk@craycos.com (Peter Klausler) writes: >If the range of your bit-reversal function is limited to chars, use a lookup >table. If your range is bigger, split your data into bytes and then use a >lookup. Reversing the bits in a char variable is tricky to say the least. The C language does not specify the number of bits in a char variable. Marv Rubinstein
henry@zoo.toronto.edu (Henry Spencer) (08/15/90)
In article <1990Aug13.185757.3236@sti.fi> ttl@sti.fi (Timo Lehtinen) writes: >What's the most optimal way to reverse the bits in an unsigned char, >i.e. change from MSB to LSB ordering ? What do you mean by "optimal"? Fastest? Most compact? On what machine? Your question has no single answer as it stands. Unless your chars have a ridiculous number of bits, as others have mentioned, a lookup table is almost certainly quickest. -- It is not possible to both understand | Henry Spencer at U of Toronto Zoology and appreciate Intel CPUs. -D.Wolfskill| henry@zoo.toronto.edu utzoo!henry
jtc@motcad.portal.com (J.T. Conklin) (08/15/90)
In article <2059@ux.acs.umn.edu> dhoyt@vw.acs.umn.edu writes: >In article <1990Aug13.185757.3236@sti.fi>, ttl@sti.fi (Timo Lehtinen) writes... >>This might be trivial, but here goes... >>What's the most optimal way to reverse the bits in an unsigned char, >>i.e. change from MSB to LSB ordering ? > > You don't have to change anything. Big and little endians only cause >trouble when you look at different integer formats. Bytes is bytes, as they >say. The question was how to flip the bits in an unsigned char, not a bytes in a word. Like has been indicated in previous postings, a 256 element lookup table is the best way to perform this task. For example, most fax machines/modems present the bits in lsb-to-msb bit order. If your G3 decompression code was written for msb-to-lsb order, bit reversal is needed. Another useful table is one that flips the bits 1-for-0,0-for-1. This is useful for inverting an image. --jtc -- J.T. Conklin UniFax Communications, Inc. CADnet Inc, San Ramon California jtc@motcad.portal.com, ...!portal!motcad!jtc
kdq@demott.COM (Kevin D. Quitt) (08/15/90)
In article <2059@ux.acs.umn.edu> dhoyt@vw.acs.umn.edu writes: >In article <1990Aug13.185757.3236@sti.fi>, ttl@sti.fi (Timo Lehtinen) writes... >>This might be trivial, but here goes... >>What's the most optimal way to reverse the bits in an unsigned char, >>i.e. change from MSB to LSB ordering ? > > You don't have to change anything. Big and little endians only cause >trouble when you look at different integer formats. Bytes is bytes, as they >say. Hey Timo, isn't this special? You don't *really* want to reverse the bits in your byte, you can just imagine them the other way around! Boy! Does that save CPU cycles, or what? -- _ Kevin D. Quitt demott!kdq kdq@demott.com DeMott Electronics Co. 14707 Keswick St. Van Nuys, CA 91405-1266 VOICE (818) 988-4975 FAX (818) 997-1190 MODEM (818) 997-4496 PEP last 96.37% of all statistics are made up.
d87-jse@alv.nada.kth.se (Joakim Sernbrant) (08/15/90)
In article <1990Aug14.203212.16248@motcad.portal.com> jtc@motcad.portal.com (J.T. Conklin) writes:
[stuff about reversing bit order removed]
Another useful table is one that flips the bits 1-for-0,0-for-1. This
is useful for inverting an image.
I can't imagine a lookup table for inverting bits can be faster or more
convenient than using xor...
Jocke
--
-- Joakim Sernbrant, Royal Institute of Technology, Stockholm, Sweden
-- Internet: d87-jse@nada.kth.se
--goudreau@larrybud.rtp.dg.com (Bob Goudreau) (08/15/90)
In article <46356@ism780c.isc.com>, news@ism780c.isc.com (News system) writes: > > Reversing the bits in a char variable is tricky to say the least. The C > language does not specify the number of bits in a char variable. What's wrong with using CHAR_BIT, which ANSI requires to be #defined in <limits.h>? ------------------------------------------------------------------------ Bob Goudreau +1 919 248 6231 Data General Corporation 62 Alexander Drive goudreau@dg-rtp.dg.com Research Triangle Park, NC 27709 ...!mcnc!rti!xyzzy!goudreau USA
jal@acc (John Lauro) (08/15/90)
In article <1990Aug14.203212.16248@motcad.portal.com> jtc@motcad.portal.com (J.T. Conklin) writes: >Another useful table is one that flips the bits 1-for-0,0-for-1. This >is useful for inverting an image. How about: (assuming 8 bit char c) c=255-c; or c^=255; - John_Lauro@ub.cc.umich.edu
austing@Apple.COM (Glenn L. Austin) (08/15/90)
jtc@motcad.portal.com (J.T. Conklin) writes: >Another useful table is one that flips the bits 1-for-0,0-for-1. This >is useful for inverting an image. How about "c ^= (char) -1"? -- ----------------------------------------------------------------------------- | Glenn L. Austin | "Turn too soon, run out of room, | | Auto Racing Enthusiast and | Turn too late, much better fate" | | Communications Toolbox Hacker | - Jim Russell Racing School Instructors | | Apple Computer, Inc. | "Drive slower, race faster" - D. Waltrip | | Internet: austing@apple.com |-------------------------------------------| | AppleLink: AUSTIN.GLENN | All opinions stated above are mine -- | | Bellnet: (408) 974-0876 | who else would want them? | -----------------------------------------------------------------------------
gvr@cs.brown.edu (George V. Reilly) (08/15/90)
In article <43975@apple.Apple.COM> austing@Apple.COM (Glenn L. Austin) writes: >jtc@motcad.portal.com (J.T. Conklin) writes: >>Another useful table is one that flips the bits 1-for-0,0-for-1. This >>is useful for inverting an image. > >How about "c ^= (char) -1"? How about ~, the built-in one's complement operator? Just mask off the high-order bits if you don't want them. output = ~input & 0xFF ________________ George V. Reilly gvr@cs.brown.edu uunet!brunix!gvr gvr@browncs.bitnet Box 1910, Brown U, Prov, RI 02912
roy@cs.umn.edu (Roy M. Silvernail) (08/15/90)
jtc@motcad.portal.com (J.T. Conklin) writes: > Another useful table is one that flips the bits 1-for-0,0-for-1. This > is useful for inverting an image. Why would you use a table for this? I'd just XOR with 0xFF. -- Roy M. Silvernail | #include <stdio.h> | Does virtual now available at: | main(){ | reality need cybrspc!roy@cs.umn.edu | float x=1; | swap space? (cyberspace... be here!)| printf("Just my $%.2f.\n",x/50);} | -- me
tsnider@enint.Wichita.NCR.COM (Tim Snider) (08/15/90)
In article <1990Aug13.185757.3236@sti.fi> ttl@sti.fi (Timo Lehtinen) writes: >What's the most optimal way to reverse the bits? Use the INMOS transputer's bit swap instruction. :) ------------------------------------------------------------------------- Tim Snider 316-636-8736 NCR Peripherial Products Div. 3718 N Rock Road. Wichita Ks. 67226 tsnider@wichita.NCR.COM
volpe@underdog.crd.ge.com (Christopher R Volpe) (08/15/90)
In article <43975@apple.Apple.COM>, austing@Apple.COM (Glenn L. Austin) writes: |>jtc@motcad.portal.com (J.T. Conklin) writes: |>>Another useful table is one that flips the bits 1-for-0,0-for-1. This |>>is useful for inverting an image. |> |>How about "c ^= (char) -1"? Works only on twos-complement machines. How about " c = ~c "?? It seems that there is a special purpose operator that does exactly and only what the question is asking, it ought to be used, no? Otherwise, what's it (the ~ operator) there for? ================== Chris Volpe G.E. Corporate R&D volpecr@crd.ge.com
browns@astro.pc.ab.com (Stan Brown, Oak Road Systems) (08/15/90)
In article <1990Aug14.233308.27889@caen.engin.umich.edu>, jal@acc (John Lauro) writes: > In article <1990Aug14.203212.16248@motcad.portal.com> jtc@motcad.portal.com (J.T. Conklin) writes: >>Another useful table is one that flips the bits 1-for-0,0-for-1. This >>is useful for inverting an image. > > How about: (assuming 8 bit char c) > c=255-c; or > c^=255; > > - John_Lauro@ub.cc.umich.edu Please, no magic numbers. You can use the bitwise-complement operator, ~ tilde (pronounced, "squiggle"). c = ~c It works on any numeric type, and the result has the same type as the operand. Typical application: to sset all the bits in n unsigned word: unsigned all_bits_set = ~(unsigned)0; -- Stan Brown, Oak Road Systems, (216) 371-0043 The opinions expressed are mine. Mine alone! Nobody else is responsible for them or even endorses them--except my cat Dexter, and he signed the power of attorney only under my threat to cut off his Cat Chow!
mayne@VSSERV.SCRI.FSU.EDU (William (Bill) Mayne) (08/15/90)
In article <1990Aug14.203212.16248@motcad.portal.com> jtc@motcad.portal.com (J.T. Conklin) writes: > >Another useful table is one that flips the bits 1-for-0,0-for-1. This >is useful for inverting an image. > > --jtc > On all the hardware I've seen inverting all the bits is done more cleanly, compactly, and probably quickly by bitwise exclusive or with a mask of all 1s. Returning to the bit reversal question, how would you or others construct the table of reversed bit bytes? In several assembly languages I've used the preprocessor would make this quite easy. In C I think I'd have to resort to either computing the table at run time or having a program compute it and write out an #include file to define it. You may infer from this that I have been somewhat spoiled and am no great fan of the very limited preprocessor facilities provided by C, though I really like the language.
stever@Octopus.COM (Steve Resnick ) (08/16/90)
In article <1990Aug14.233308.27889@caen.engin.umich.edu> jal@acc (John Lauro) writes: >In article <1990Aug14.203212.16248@motcad.portal.com> jtc@motcad.portal.com (J.T. Conklin) writes: >>Another useful table is one that flips the bits 1-for-0,0-for-1. This >>is useful for inverting an image. > >How about: (assuming 8 bit char c) > c=255-c; or > c^=255; > Why not use: ~c? on most machines I expect it would save CPU cycles as well as instructions. Cheers! Steve -- ---------------------------------------------------------------------------- steve.resnick@f105.n143.z1@FIDONET.ORG #include<std_disclaimer.h> Flames, grammar errors, spelling errrors >/dev/nul ----------------------------------------------------------------------------
bright@Data-IO.COM (Walter Bright) (08/16/90)
In article <1990Aug13.185757.3236@sti.fi> ttl@sti.fi (Timo Lehtinen) writes: <This might be trivial, but here goes... <What's the most optimal way to reverse the bits in an unsigned char, <i.e. change from MSB to LSB ordering ? unsigned char mirror[256] = { 0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0, 0x08,0x88,0x48,0xC8,0x28,0xA8,0x68,0xE8,0x18,0x98,0x58,0xD8,0x38,0xB8,0x78,0xF8, 0x04,0x84,0x44,0xC4,0x24,0xA4,0x64,0xE4,0x14,0x94,0x54,0xD4,0x34,0xB4,0x74,0xF4, 0x0C,0x8C,0x4C,0xCC,0x2C,0xAC,0x6C,0xEC,0x1C,0x9C,0x5C,0xDC,0x3C,0xBC,0x7C,0xFC, 0x02,0x82,0x42,0xC2,0x22,0xA2,0x62,0xE2,0x12,0x92,0x52,0xD2,0x32,0xB2,0x72,0xF2, 0x0A,0x8A,0x4A,0xCA,0x2A,0xAA,0x6A,0xEA,0x1A,0x9A,0x5A,0xDA,0x3A,0xBA,0x7A,0xFA, 0x06,0x86,0x46,0xC6,0x26,0xA6,0x66,0xE6,0x16,0x96,0x56,0xD6,0x36,0xB6,0x76,0xF6, 0x0E,0x8E,0x4E,0xCE,0x2E,0xAE,0x6E,0xEE,0x1E,0x9E,0x5E,0xDE,0x3E,0xBE,0x7E,0xFE, 0x01,0x81,0x41,0xC1,0x21,0xA1,0x61,0xE1,0x11,0x91,0x51,0xD1,0x31,0xB1,0x71,0xF1, 0x09,0x89,0x49,0xC9,0x29,0xA9,0x69,0xE9,0x19,0x99,0x59,0xD9,0x39,0xB9,0x79,0xF9, 0x05,0x85,0x45,0xC5,0x25,0xA5,0x65,0xE5,0x15,0x95,0x55,0xD5,0x35,0xB5,0x75,0xF5, 0x0D,0x8D,0x4D,0xCD,0x2D,0xAD,0x6D,0xED,0x1D,0x9D,0x5D,0xDD,0x3D,0xBD,0x7D,0xFD, 0x03,0x83,0x43,0xC3,0x23,0xA3,0x63,0xE3,0x13,0x93,0x53,0xD3,0x33,0xB3,0x73,0xF3, 0x0B,0x8B,0x4B,0xCB,0x2B,0xAB,0x6B,0xEB,0x1B,0x9B,0x5B,0xDB,0x3B,0xBB,0x7B,0xFB, 0x07,0x87,0x47,0xC7,0x27,0xA7,0x67,0xE7,0x17,0x97,0x57,0xD7,0x37,0xB7,0x77,0xF7, 0x0F,0x8F,0x4F,0xCF,0x2F,0xAF,0x6F,0xEF,0x1F,0x9F,0x5F,0xDF,0x3F,0xBF,0x7F,0xFF, }; To use: mc = mirror[(unsigned char) c];
bright@Data-IO.COM (Walter Bright) (08/16/90)
In article <1990Aug14.203212.16248@motcad.portal.com> jtc@motcad.portal.com (J.T. Conklin) writes:
<Another useful table is one that flips the bits 1-for-0,0-for-1. This
<is useful for inverting an image.
What's wrong with:
c = ~c;
?fpb@ittc.wec.com (Frank P. Bresz) (08/16/90)
In article <464.26c93018@astro.pc.ab.com> browns@astro.pc.ab.com (Stan Brown, Oak Road Systems) writes: >Please, no magic numbers. You can use the bitwise-complement operator, ~ tilde >(pronounced, "squiggle"). > c = ~c >It works on any numeric type, and the result has the same type as the operand. >Typical application: to sset all the bits in n unsigned word: Great solution obviously but it is not (pronounced, "squiggle"). its pronounced tilda. -- +--------------------+ |fbresz@ittc.wec.com | My opinions are my own, I'm not paid |uunet!ittc!fbresz | enough to make an official statement |(412)733-6749 | +-----------------------------------+ |Fax: (412)733-6444 | | THIS SPACE FOR SALE!!! | +--------------------+ +-----------------------------------+
maunz@warwick.ac.uk (R. Turner) (08/16/90)
In article <FPB.90Aug15201012@ittc.ittc.wec.com> fbresz@ittc.wec.com writes: >In article <464.26c93018@astro.pc.ab.com> browns@astro.pc.ab.com (Stan Brown, Oak Road Systems) writes: > > >>Please, no magic numbers. You can use the bitwise-complement operator, >>~ tilde >>(pronounced, "squiggle"). >> c = ~c > > Great solution obviously but it is not (pronounced, "squiggle"). >its pronounced tilda. I'm in favour of compromises. I pronounce it "twiddle". What's in a name? :) \x/inja == Keith R. Turner == maunz@uk.ac.warwick.cu "Winja? It's short for Teenage Student Winja Turbot."
martin@mwtech.UUCP (Martin Weitzel) (08/16/90)
In article <401@sun13.scri.fsu.edu> mayne@VSSERV.SCRI.FSU.EDU (William (Bill) Mayne) writes: >Returning to the bit reversal question, how would you or others >construct the table of reversed bit bytes? In several assembly >languages I've used the preprocessor would make this quite easy. Yes, but was it done in the same way with all those preprocessors? Note that C is a portable language, which said assemblers surely were not. I don't say that the C preprocessor must be limited in its features because the portability of C. It's only that I would allways prefer C *despite* its limited preprocessor because of portabiliy. >In C I think I'd have to resort to either computing the table >at run time or having a program compute it and write out an >#include file to define it. IMHO the latter is a very clean, friendly, and portable approach. Whom does it hurt (especially if you use "make" to manage your project and produce those generated files automatically before the ones that include them)? A programmer who knows C will have to learn nothing new about esoteric preprocessor features and still understand what is done, as the initializing program is written in C. BTW: If the C preprocessor were ever extended to have loops and more (in C-2001?), I fear we programmers would have to learn just another language. Of course, it would be a nice idea if an enhanced preprocessor could be made somehow an interpreter for a subset of C, so that there were not to learn much new. >You may infer from this that I have >been somewhat spoiled and am no great fan of the very limited >preprocessor facilities provided by C, though I really like the >language. If you like the C language, you probably like UNIX too and there you have an alternative if the C preprocessor is too limited: "m4". Again back to the original question. I too would use a table, but after some discussion in this thread I got curious how much code it would afford to reverse bit patterns "on the fly". So I've written the following short program, which is a bit generalized so that it can be used for bit patterns of arbitrary length up to the size of an unsigned int. -------------------------------------------------------------------- /* * Bit-Reversal Makro: * Treat b as a pattern of n bits, counting * from 0 (least significant) to n-1 (most * significant). R(b,i,n) returns the i-th * bit in its reversed position n-1-i. */ #define R(b,i,n) ((i) < ((n)+1)/2)\ ? ((b) & (1<<(i))) << ((n) - 2*(i) - 1)\ : ((b) & (1<<(i))) >> (2*(i) - (n) + 1) /* * Pattern-Reversal Function: * Reverse the bit pattern specified in b, * with respect to its n least significant * bits. Return reversed pattern as result. */ unsigned int revbits(b, n) unsigned int b; int n; { register int i, k; for (i = k = 0; i < n; i++) k |= R(b, i, n); return k; } #ifdef TEST void printbits(b, n, s) unsigned int b; int n; char *s; { while (n-- > 0) putchar(b & (1<<n) ? '1' : '0'); while (*s) putchar(*s++); } main(argc, argv) int argc; char *argv[]; { while (*++argv) { int a, i, ts = atoi(*argv); if (ts <= 0) continue; a = 1; while ((~0 << a) & ts-1) a++; for (i = 0; i < ts; i++) { printbits(i, a, " -- "); printbits(revbits(i, a), a, "\n"); } } } #endif -------------------------------------------------------------------- Compiling this on an 80386 (with TEST not defined, of course) shows only 112 bytes of code, so that it is well below the size of a table required to invert 8 bits (for a char). Of course, you can use the revbits function to (dynamically) initialize a table, if speed is the problem, or you can use it as a base for writing static initializations of tables as the poster (Bill) proposed above. -- Martin Weitzel, email: martin@mwtech.UUCP, voice: 49-(0)6151-6 56 83
karl@haddock.ima.isc.com (Karl Heuer) (08/17/90)
>>>~ tilde (pronounced, "squiggle"). >>its pronounced tilda. >I pronounce it "twiddle". It's octosplatch! Everybody knows that! I learned it when I was growing up in West Dakota, and I am 257 years old! Seriously, folks, let's not start this again. All the various pronouncations can be found in either the Hacker's Dictionary aka Jargon File, or the FAQ list in comp.unix.questions, and *we don't care which one you like best*. Please keep it off this newsgroup. Karl W. Z. Heuer (karl@kelp.ima.isc.com or ima!kelp!karl), The Walking Lint
bilbo@bisco.kodak.COM (Charles Tryon) (08/25/90)
In message <2059@ux.acs.umn.edu>, dhoyt@vw.acs.umn.edu writes > In article <1990Aug13.185757.3236@sti.fi>, ttl@sti.fi (Timo Lehtinen) writes... > >This might be trivial, but here goes... > >What's the most optimal way to reverse the bits in an unsigned char, > >i.e. change from MSB to LSB ordering ? > > You don't have to change anything. Big and little endians only cause > trouble when you look at different integer formats. Bytes is bytes, as they > say. > > Everyone thinks that 2^128 is 10000000. The trouble arises with characters > packed into integers. Everyone knows that in 'abcd' 'a' is the first > character. But if packed into an integer on a dec, intel or national semi > machine the string would read 'dcba.' That is the first letter, 'a', will be > in the Least Significant BYTE. Most others would say the integer would look > like 'abcd.' The first character is the Most Significant BYTE. ..(stuff deleted).. > unions, you shouldn't ever have problems. > > Except when you do binary ftp's or swap binary (not character!) data with > machines on the wild side. I am looking at doing just this! We are working on Sun 3/80 systems and porting to a Sparc station. In the process, we are thinking of what might happen if we wanted to go to some other system (read that, "IBM") which uses the "wrong" byte order. Sun has a package called XDR (for eXternal Data Representation) which I am looking at. Are there any other portability "standards" that people out there have seen/used which might be more widely accepted for this sort of thing? > david paul hoyt | dhoyt@vx.acs.umn.edu | dhoyt@umnacvx.bitnet -- Chuck Tryon (PLEASE use this address, as Kodak foobars one in header!) <bilbo@bisco.kodak.com> USmail: 46 Post Ave.;Roch. NY 14619 B. Baggins <<...include standard disclamer...>> At Your Service "Then again, squirrels could be stupid." (D. Mocsny)
jvb7u@astsun.astro.Virginia.EDU (Jon Brinkmann) (08/25/90)
In article <9008241924.AA00274@bisco.kodak.COM> nobody@Kodak.COM writes:
#> >This might be trivial, but here goes...
#> >What's the most optimal way to reverse the bits in an unsigned char,
#> >i.e. change from MSB to LSB ordering ?
#
# I am looking at doing just this! We are working on Sun 3/80 systems and
#porting to a Sparc station. In the process, we are thinking of what might
#happen if we wanted to go to some other system (read that, "IBM") which uses
#the "wrong" byte order.
The sender isn't talking about BYTE order, he's talking about BIT order.
They are obviously NOT the same! Byte order is trivially handled on most
machines. There was an extensive discussion in this newsgroup about a year
ago. Check the archives.
Now about bit order. Most processors don't handle bits individually. You'll
have to check each bit in the source and set the appropriate bit in the
destination. Something like
for (i = dest = 0, j = 1; i < 8; i++, j << 1)
if (source & j) dest |= 1 << (7 - i);
Jon
---
--
Jon Brinkmann Astronomy Department
Internet: jvb7u@Virginia.EDU University of Virginia
UUCP: ...!uunet!virginia!jvb7u P.O. Box 3818
SPAN/HEPnet: 6654::jvb7u Charlottesville, VA 22903-0818