binary.cpp

00001 ///\file
00002 
00003 /******************************************************************************
00004 The MIT License(MIT)
00005 
00006 Embedded Template Library.
00007 https://github.com/ETLCPP/etl
00008 http://www.etlcpp.com
00009 
00010 Copyright(c) 2017 jwellbelove
00011 
00012 Permission is hereby granted, free of charge, to any person obtaining a copy
00013 of this software and associated documentation files(the "Software"), to deal
00014 in the Software without restriction, including without limitation the rights
00015 to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
00016 copies of the Software, and to permit persons to whom the Software is
00017 furnished to do so, subject to the following conditions :
00018 
00019 The above copyright notice and this permission notice shall be included in all
00020 copies or substantial portions of the Software.
00021 
00022 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00023 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00024 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
00025 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
00026 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
00027 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
00028 SOFTWARE.
00029 ******************************************************************************/
00030 
00031 #include "platform.h "
00032 #include "binary.h "
00033 
00034 namespace etl
00035 {
00036 #if ETL_8BIT_SUPPORT
00037   //***************************************************************************
00038   /// Reverse 8 bits.
00039   //***************************************************************************
00040   uint8_t reverse_bits(uint8_t value)
00041   {
00042     value = ((value & 0xAA) >> 1) | ((value & 0x55) << 1);
00043     value = ((value & 0xCC) >> 2) | ((value & 0x33) << 2);
00044     value = (value >> 4) | (value << 4);
00045 
00046     return value;
00047   }
00048 #endif
00049 
00050   //***************************************************************************
00051   /// Reverse 16 bits.
00052   //***************************************************************************
00053   uint16_t reverse_bits(uint16_t value)
00054   {
00055     value = ((value & 0xAAAA) >> 1) | ((value & 0x5555) << 1);
00056     value = ((value & 0xCCCC) >> 2) | ((value & 0x3333) << 2);
00057     value = ((value & 0xF0F0) >> 4) | ((value & 0x0F0F) << 4);
00058     value = (value >> 8) | (value << 8);
00059 
00060     return value;
00061   }
00062  
00063   //***************************************************************************
00064   /// Reverse 32 bits.
00065   //***************************************************************************
00066   uint32_t reverse_bits(uint32_t value)
00067   {
00068     value = ((value & 0xAAAAAAAA) >>  1) | ((value & 0x55555555) <<  1);
00069     value = ((value & 0xCCCCCCCC) >>  2) | ((value & 0x33333333) <<  2);
00070     value = ((value & 0xF0F0F0F0) >>  4) | ((value & 0x0F0F0F0F) <<  4);
00071     value = ((value & 0xFF00FF00) >>  8) | ((value & 0x00FF00FF) <<  8);
00072     value = (value >> 16) | (value << 16);
00073 
00074     return value;
00075   }
00076 
00077   //***************************************************************************
00078   /// Reverse 64 bits.
00079   //***************************************************************************
00080   uint64_t reverse_bits(uint64_t value)
00081   {
00082     value = ((value & 0xAAAAAAAAAAAAAAAA) >>  1) | ((value & 0x5555555555555555) <<  1);
00083     value = ((value & 0xCCCCCCCCCCCCCCCC) >>  2) | ((value & 0x3333333333333333) <<  2);
00084     value = ((value & 0xF0F0F0F0F0F0F0F0) >>  4) | ((value & 0x0F0F0F0F0F0F0F0F) <<  4);
00085     value = ((value & 0xFF00FF00FF00FF00) >>  8) | ((value & 0x00FF00FF00FF00FF) <<  8);
00086     value = ((value & 0xFFFF0000FFFF0000) >> 16) | ((value & 0x0000FFFF0000FFFF) << 16);
00087     value = (value >> 32) | (value << 32);
00088 
00089     return value;
00090   }
00091 
00092   //***************************************************************************
00093   /// Reverse bytes 16 bit.
00094   //***************************************************************************
00095   uint16_t reverse_bytes(uint16_t value)
00096   {
00097     value = (value >> 8) | (value << 8);
00098 
00099     return value;
00100   }
00101 
00102   //***************************************************************************
00103   /// Reverse bytes 32 bit.
00104   //***************************************************************************
00105   uint32_t reverse_bytes(uint32_t value)
00106   {
00107     value = ((value & 0xFF00FF00) >> 8) | ((value & 0x00FF00FF) << 8);
00108     value = (value >> 16) | (value << 16);
00109 
00110     return value;
00111   }
00112   
00113   //***************************************************************************
00114   /// Reverse bytes 64 bit.
00115   //***************************************************************************
00116   uint64_t reverse_bytes(uint64_t value)
00117   {
00118     value = ((value & 0xFF00FF00FF00FF00) >> 8)  | ((value & 0x00FF00FF00FF00FF) << 8);
00119     value = ((value & 0xFFFF0000FFFF0000) >> 16) | ((value & 0x0000FFFF0000FFFF) << 16);
00120     value = (value >> 32) | (value << 32);
00121 
00122     return value;
00123   }
00124 
00125 #if ETL_8BIT_SUPPORT
00126   //***************************************************************************
00127   /// Converts Gray code to binary.
00128   //***************************************************************************
00129   uint8_t gray_to_binary(uint8_t value)
00130   {
00131     value ^= (value >> 4);
00132     value ^= (value >> 2);
00133     value ^= (value >> 1);
00134 
00135     return value;
00136   }
00137 #endif
00138 
00139   //***************************************************************************
00140   /// Converts Gray code to binary.
00141   //***************************************************************************
00142   uint16_t gray_to_binary(uint16_t value)
00143   {
00144     value ^= (value >> 8);
00145     value ^= (value >> 4);
00146     value ^= (value >> 2);
00147     value ^= (value >> 1);
00148 
00149     return value;
00150   }
00151 
00152   //***************************************************************************
00153   /// Converts Gray code to binary.
00154   //***************************************************************************
00155   uint32_t gray_to_binary(uint32_t value)
00156   {
00157     value ^= (value >> 16);
00158     value ^= (value >> 8);
00159     value ^= (value >> 4);
00160     value ^= (value >> 2);
00161     value ^= (value >> 1);
00162 
00163     return value;
00164   }
00165 
00166   //***************************************************************************
00167   /// Converts Gray code to binary.
00168   //***************************************************************************
00169   uint64_t gray_to_binary(uint64_t value)
00170   {
00171     value ^= (value >> 32);
00172     value ^= (value >> 16);
00173     value ^= (value >> 8);
00174     value ^= (value >> 4);
00175     value ^= (value >> 2);
00176     value ^= (value >> 1);
00177 
00178     return value;
00179   }
00180 
00181 #if ETL_8BIT_SUPPORT
00182   //***************************************************************************
00183   /// Count set bits. 8 bits.
00184   //***************************************************************************
00185   uint_least8_t count_bits(uint8_t value)
00186   {
00187     uint32_t count;
00188     static const int S[] = { 1, 2, 4 };
00189     static const uint8_t B[] = { 0x55, 0x33, 0x0F };
00190 
00191     count = value - ((value >> 1) & B[0]);
00192     count = ((count >> S[1]) & B[1]) + (count & B[1]);
00193     count = ((count >> S[2]) + count) & B[2];
00194 
00195     return uint_least8_t(count);
00196   }
00197 #endif
00198 
00199   //***************************************************************************
00200   /// Count set bits. 16 bits.
00201   //***************************************************************************
00202   uint_least8_t count_bits(uint16_t value)
00203   {
00204     uint32_t count;
00205     static const int S[] = { 1, 2, 4, 8 };
00206     static const uint16_t B[] = { 0x5555, 0x3333, 0x0F0F, 0x00FF };
00207 
00208     count = value - ((value >> 1) & B[0]);
00209     count = ((count >> S[1]) & B[1]) + (count & B[1]);
00210     count = ((count >> S[2]) + count) & B[2];
00211     count = ((count >> S[3]) + count) & B[3];
00212 
00213     return count;
00214   }
00215 
00216   //***************************************************************************
00217   /// Count set bits. 32 bits.
00218   //***************************************************************************
00219   uint_least8_t count_bits(uint32_t value)
00220   {
00221     uint32_t count;
00222 
00223     value = value - ((value >> 1) & 0x55555555);
00224     value = (value & 0x33333333) + ((value >> 2) & 0x33333333);
00225     count = (((value + (value >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
00226 
00227     return uint_least8_t(count);
00228   }
00229 
00230   //***************************************************************************
00231   /// Count set bits. 64 bits.
00232   //***************************************************************************
00233   uint_least8_t count_bits(uint64_t value)
00234   {
00235     uint64_t count;
00236     static const int S[] = { 1, 2, 4, 8, 16, 32 };
00237     static const uint64_t B[] = { 0x5555555555555555, 0x3333333333333333, 0x0F0F0F0F0F0F0F0F, 0x00FF00FF00FF00FF, 0x0000FFFF0000FFFF, 0x00000000FFFFFFFF };
00238 
00239     count = value - ((value >> 1) & B[0]);
00240     count = ((count >> S[1]) & B[1]) + (count & B[1]);
00241     count = ((count >> S[2]) + count) & B[2];
00242     count = ((count >> S[3]) + count) & B[3];
00243     count = ((count >> S[4]) + count) & B[4];
00244     count = ((count >> S[5]) + count) & B[5];
00245 
00246     return uint_least8_t(count);
00247   }
00248 
00249 #if ETL_8BIT_SUPPORT
00250   //***************************************************************************
00251   /// Parity. 8bits. 0 = even, 1 = odd
00252   //***************************************************************************
00253   uint_least8_t parity(uint8_t value)
00254   {
00255     value ^= value >> 4;
00256     value &= 0x0F;
00257     return (0x6996 >> value) & 1;
00258   }
00259 #endif
00260 
00261   //***************************************************************************
00262   /// Parity. 16bits. 0 = even, 1 = odd
00263   //***************************************************************************
00264   uint_least8_t parity(uint16_t value)
00265   {
00266     value ^= value >> 8;
00267     value ^= value >> 4;
00268     value &= 0x0F;
00269     return (0x6996 >> value) & 1;
00270   }
00271 
00272   //***************************************************************************
00273   /// Parity. 32bits. 0 = even, 1 = odd
00274   //***************************************************************************
00275   uint_least8_t parity(uint32_t value)
00276   {
00277     value ^= value >> 16;
00278     value ^= value >> 8;
00279     value ^= value >> 4;
00280     value &= 0x0F;
00281     return (0x6996 >> value) & 1;
00282   }
00283 
00284   //***************************************************************************
00285   /// Parity. 64bits. 0 = even, 1 = odd
00286   //***************************************************************************
00287   uint_least8_t parity(uint64_t value)
00288   {
00289     value ^= value >> 32;
00290     value ^= value >> 16;
00291     value ^= value >> 8;
00292     value ^= value >> 4;
00293     value &= 0x0F;
00294     return (0x69966996 >> value) & 1;
00295   }
00296 
00297 #if ETL_8BIT_SUPPORT
00298   //***************************************************************************
00299   /// Count trailing zeros. bit.
00300   /// Uses a binary search.
00301   //***************************************************************************
00302   uint_least8_t count_trailing_zeros(uint8_t value)
00303   {
00304     uint_least8_t count;
00305 
00306     if (value & 0x1)
00307     {
00308       count = 0;
00309     }
00310     else
00311     {
00312       count = 1;
00313 
00314       if ((value & 0xF) == 0)
00315       {
00316         value >>= 4;
00317         count += 4;
00318       }
00319 
00320       if ((value & 0x3) == 0)
00321       {
00322         value >>= 2;
00323         count += 2;
00324       }
00325 
00326       count -= value & 0x1;
00327     }
00328 
00329     return count;
00330   }
00331 #endif
00332 
00333   //***************************************************************************
00334   /// Count trailing zeros. 16bit.
00335   /// Uses a binary search.
00336   //***************************************************************************
00337   uint_least8_t count_trailing_zeros(uint16_t value)
00338   {
00339     uint_least8_t count;
00340 
00341     if (value & 0x1)
00342     {
00343       count = 0;
00344     }
00345     else
00346     {
00347       count = 1;
00348 
00349       if ((value & 0xFF) == 0)
00350       {
00351         value >>= 8;
00352         count += 8;
00353       }
00354 
00355       if ((value & 0xF) == 0)
00356       {
00357         value >>= 4;
00358         count += 4;
00359       }
00360 
00361       if ((value & 0x3) == 0)
00362       {
00363         value >>= 2;
00364         count += 2;
00365       }
00366 
00367       count -= value & 0x1;
00368     }
00369 
00370     return count;
00371   }
00372 
00373   //***************************************************************************
00374   /// Count trailing zeros. 32bit.
00375   /// Uses a binary search.
00376   //***************************************************************************
00377   uint_least8_t count_trailing_zeros(uint32_t value)
00378   {
00379     uint_least8_t count;
00380 
00381     if (value & 0x1)
00382     {
00383       count = 0;
00384     }
00385     else
00386     {
00387       count = 1;
00388 
00389       if ((value & 0xFFFF) == 0)
00390       {
00391         value >>= 16;
00392         count += 16;
00393       }
00394 
00395       if ((value & 0xFF) == 0)
00396       {
00397         value >>= 8;
00398         count += 8;
00399       }
00400 
00401       if ((value & 0xF) == 0)
00402       {
00403         value >>= 4;
00404         count += 4;
00405       }
00406 
00407       if ((value & 0x3) == 0)
00408       {
00409         value >>= 2;
00410         count += 2;
00411       }
00412 
00413       count -= value & 0x1;
00414     }
00415 
00416     return count;
00417   }
00418 
00419   //***************************************************************************
00420   /// Count trailing zeros. 64bit.
00421   /// Uses a binary search.
00422   //***************************************************************************
00423   uint_least8_t count_trailing_zeros(uint64_t value)
00424   {
00425       uint_least8_t count;
00426 
00427       if (value & 0x1)
00428       {
00429         count = 0;
00430       }
00431       else
00432       {
00433         count = 1;
00434 
00435         if ((value & 0xFFFFFFFF) == 0)
00436         {
00437           value >>= 32;
00438           count += 32;
00439         }
00440 
00441         if ((value & 0xFFFF) == 0)
00442         {
00443           value >>= 16;
00444           count += 16;
00445         }
00446 
00447         if ((value & 0xFF) == 0)
00448         {
00449           value >>= 8;
00450           count += 8;
00451         }
00452 
00453         if ((value & 0xF) == 0)
00454         {
00455           value >>= 4;
00456           count += 4;
00457         }
00458 
00459         if ((value & 0x3) == 0)
00460         {
00461           value >>= 2;
00462           count += 2;
00463         }
00464 
00465         count -= value & 0x1;
00466       }
00467 
00468       return count;
00469   }
00470 }
00471