Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.postscript > #3201 > unrolled thread

Reversing the bits in a byte

Back to article view | Back to comp.lang.postscript

Contents

  Reversing the bits in a byte luser droog <luser.droog@gmail.com> - 2017-12-01 21:28 -0800
    Re: Reversing the bits in a byte Carlos <carlos@cvkm.cz> - 2017-12-02 12:46 +0100
      Re: Reversing the bits in a byte jdaw1 <jdawiseman@gmail.com> - 2017-12-03 11:58 -0800
        Re: Reversing the bits in a byte luser droog <luser.droog@gmail.com> - 2017-12-04 08:54 -0800
    Re: Reversing the bits in a byte nemo2e4@googlemail.com - 2017-12-05 09:43 -0800
      Re: Reversing the bits in a byte nemo20000 <nemo2e4@googlemail.com> - 2017-12-05 09:58 -0800
        Re: Reversing the bits in a byte luser droog <luser.droog@gmail.com> - 2017-12-05 14:31 -0800
      Re: Reversing the bits in a byte luser droog <luser.droog@gmail.com> - 2017-12-05 15:11 -0800

#3201 — Reversing the bits in a byte

I was re-reading some old posts of mine on stackoverflow and stumbled upon
this one where I went off on an unproductive tangent attempting to explain
how to get image samples to feed to the `image` operator.

  https://stackoverflow.com/questions/15167454/how-include-img-in-postscript/15183845?s=10|25.9455#15183845

And I showed this long decorated function to a friend of mine who immediately
recalled that there's an algorithm for rotating a 2D-bitmap which simplifies
to 1D nicely. First the old, ugly one:

%reverse the bits in a byte
/reverse {               % b
    dup 1 and            % b b0          % explode the bits
    1 index 2 and        % b b0 b1
    2 index 4 and        % b b0 b1 b2
    3 index 8 and        % b b0 b1 b2 b3
    4 index 16 and       % b b0 b1 b2 b3 b4
    5 index 32 and       % b b0 b1 b2 b3 b4 b5
    6 index 64 and       % b b0 b1 b2 b3 b4 b5 b6
    8 7 roll 128 and     % b0 b1 b2 b3 b4 b5 b6 b7
    -7 bitshift exch     % b0 b1 b2 b3 b4 b5 b7-7=0' b6  % shift and combine
    -5 bitshift or exch  % b0 b1 b2 b3 b4 b0'|b6-5=1' b5
    -3 bitshift or exch  % b0 b1 b2 b3 b0'|b1'|b5-3=2' b4
    -1 bitshift or exch  % b0 b1 b2 b0'|b1'|b2'|b4-1=3' b3
    1 bitshift or exch   % b0 b1 b0'|b1'|b2'|b3'|b3+1=4' b2
    3 bitshift or exch   % b0 b0'|b1'|b2'|b3'|b4'|b2+3=5' b1
    5 bitshift or exch   % b0'|b1'|b2'|b3'|b4'|b5'|b1+5=6' b0
    7 bitshift or        % b0'|b1'|b2'|b3'|b4'|b5'|b6'|b0+7=7'
} def


Now applying this new idea, which I have also explained at:

  https://codereview.stackexchange.com/a/181823/5912

I get this, which appears much simpler:

/reverse8 {
    dup 4 bitshift exch -4 bitshift or
    dup 16#33 and 2 bitshift exch 16#cc and -2 bitshift or
    dup 16#55 and 1 bitshift exch 16#aa and -1 bitshift or
} def

Exchange the two nibbles, then exchange chomps (?) in each nibble,
then exchange the bits in each chomp. Is there any better way?

[toc] | [next] | [standalone]

#3202

[luser droog <luser.droog@gmail.com>, 2017-12-01 21:28]
[...]
> %reverse the bits in a byte
[...]
> Now applying this new idea, which I have also explained at:
> 
>   https://codereview.stackexchange.com/a/181823/5912
> 
> I get this, which appears much simpler:
> 
> /reverse8 {
>     dup 4 bitshift exch -4 bitshift or
>     dup 16#33 and 2 bitshift exch 16#cc and -2 bitshift or
>     dup 16#55 and 1 bitshift exch 16#aa and -1 bitshift or
> } def
> 
> Exchange the two nibbles, then exchange chomps (?) in each nibble,
> then exchange the bits in each chomp. Is there any better way?

Another possibility is to use a lookup array. (I don't know which one is faster
or better.)
-- 

[toc] | [prev] | [next] | [standalone]

#3203

Surely that’s what dictionaries are for? 

<< 0 0 1 128 2 64 3 192 4 32 5 160 6 96 7 224 8 16 9 144 10 80 11 208 12 48 13 176 14 112 15 240 16 8 17 136 18 72 19 200 20 40 21 168 22 104 23 232 24 24 25 152 26 88 27 216 28 56 29 184 30 120 31 248 32 4 33 132 34 68 35 196 36 36 37 164 38 100 39 228 40 20 41 148 42 84 43 212 44 52 45 180 46 116 47 244 48 12 49 140 50 76 51 204 52 44 53 172 54 108 55 236 56 28 57 156 58 92 59 220 60 60 61 188 62 124 63 252 64 2 65 130 66 66 67 194 68 34 69 162 70 98 71 226 72 18 73 146 74 82 75 210 76 50 77 178 78 114 79 242 80 10 81 138 82 74 83 202 84 42 85 170 86 106 87 234 88 26 89 154 90 90 91 218 92 58 93 186 94 122 95 250 96 6 97 134 98 70 99 198 100 38 101 166 102 102 103 230 104 22 105 150 106 86 107 214 108 54 109 182 110 118 111 246 112 14 113 142 114 78 115 206 116 46 117 174 118 110 119 238 120 30 121 158 122 94 123 222 124 62 125 190 126 126 127 254 128 1 129 129 130 65 131 193 132 33 133 161 134 97 135 225 136 17 137 145 138 81 139 209 140 49 141 177 142 113 143 241 144 9 145 137 146 73 147 201 148 41 149 169 150 105 151 233 152 25 153 153 154 89 155 217 156 57 157 185 158 121 159 249 160 5 161 133 162 69 163 197 164 37 165 165 166 101 167 229 168 21 169 149 170 85 171 213 172 53 173 181 174 117 175 245 176 13 177 141 178 77 179 205 180 45 181 173 182 109 183 237 184 29 185 157 186 93 187 221 188 61 189 189 190 125 191 253 192 3 193 131 194 67 195 195 196 35 197 163 198 99 199 227 200 19 201 147 202 83 203 211 204 51 205 179 206 115 207 243 208 11 209 139 210 75 211 203 212 43 213 171 214 107 215 235 216 27 217 155 218 91 219 219 220 59 221 187 222 123 223 251 224 7 225 135 226 71 227 199 228 39 229 167 230 103 231 231 232 23 233 151 234 87 235 215 236 55 237 183 238 119 239 247 240 15 241 143 242 79 243 207 244 47 245 175 246 111 247 239 248 31 249 159 250 95 251 223 252 63 253 191 254 127 255 255 >>

[toc] | [prev] | [next] | [standalone]

#3204

On Sunday, December 3, 2017 at 1:59:00 PM UTC-6, jdaw1 wrote:
> Surely that’s what dictionaries are for? 
> 
> << snip >>

Yes a dictionary will probably be faster than doing the arithmetic
in PostScript. In xpost this will certainly be the case, because
executing more "objects" invokes the interpreter overhead more times.

But since the input is (presumably) limited, I think an array wins
for speed here. 


/reverse8 {
    dup 4 bitshift exch -4 bitshift or
    dup 16#33 and 2 bitshift exch 16#cc and -2 bitshift or
    dup 16#55 and 1 bitshift exch 16#aa and -1 bitshift or
} def

/reverse8array [ 0 1 256 { reverse8 } for ] def

/reverse8 {
    //reverse8array exch  % 16#ff and   %% TODO use 'and'?                                                                                                                                                                        
    get
} def

currentdict /reverse8array undef


If we're suspcious about the input, it may be wise to to
trim it to 8 bits. For the upthread example, the values
can be trusted since they come straight from the file
and the decoder guarantees the width of the values.

[toc] | [prev] | [next] | [standalone]

#3205

There’s no need to keep it in the bottom 8 bits during the flip. Move it back down at the end. Saves some shifts.

[toc] | [prev] | [next] | [standalone]

#3206

Oh, and don't use a dictionary OR an array.

If you must do a lookup, use a string.

[toc] | [prev] | [next] | [standalone]

#3207

On Tuesday, December 5, 2017 at 11:58:30 AM UTC-6, nemo20000 wrote:
> Oh, and don't use a dictionary OR an array.
> 
> If you must do a lookup, use a string.

A string would certainly be more space-efficient. Although the 
size in question might make the difference not particularly
significant.

As far as time-efficiency, I suspect this may depend on the particulars
of the PostScript interpreter being used. With xpost, I think the array
may be faster because the integer values are already constructed into
integer objects, and indexing from a string will have to construct a 
new integer object for the result. This is not a lengthy operation, but
it is an extra thing that string indexing needs to do which is not 
needed for array indexing.

I feel a need for some means of profiling these things...

[toc] | [prev] | [next] | [standalone]

#3208

On Tuesday, December 5, 2017 at 11:43:58 AM UTC-6, nem...@googlemail.com wrote:
> There’s no need to keep it in the bottom 8 bits during the flip. Move it back down at the end. Saves some shifts.

That's interesting. Where's my pencil?....

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.postscript

csiph-web