crc.hpp 93 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316
  1. // Boost CRC library crc.hpp header file -----------------------------------//
  2. // Copyright 2001, 2004, 2011 Daryle Walker.
  3. // Distributed under the Boost Software License, Version 1.0. (See the
  4. // accompanying file LICENSE_1_0.txt or a copy at
  5. // <http://www.boost.org/LICENSE_1_0.txt>.)
  6. // See <http://www.boost.org/libs/crc/> for the library's home page.
  7. /** \file
  8. \brief A collection of function templates and class templates that compute
  9. various forms of Cyclic Redundancy Codes (CRCs).
  10. \author Daryle Walker
  11. \version 1.5
  12. \copyright Boost Software License, version 1.0
  13. Contains the declarations (and definitions) of various kinds of CRC
  14. computation functions, function object types, and encapsulated policy types.
  15. \warning The sample CRC-computer types were just checked against the
  16. <a href="http://regregex.bbcmicro.net/crc-catalogue.htm">Catalogue of
  17. parametrised CRC algorithms</a>. New type aliases were added where I got
  18. a standard wrong. However, the mistaken <code>typedef</code>s are still
  19. there for backwards compatibility.
  20. \note There are references to the <i>Rocksoft&trade; Model CRC
  21. Algorithm</i>, as described within \"A Painless Guide to CRC Error
  22. Detection Algorithms,\" linked from \"<a
  23. href="http://www.ross.net/crc/crcpaper.html">CRC: A Paper On CRCs</a>\" by
  24. Ross Williams. It will be abbreviated \"RMCA\" in other documentation
  25. blocks.
  26. */
  27. #ifndef BOOST_CRC_HPP
  28. #define BOOST_CRC_HPP
  29. #include <boost/array.hpp> // for boost::array
  30. #include <boost/config.hpp> // for BOOST_STATIC_CONSTANT, etc.
  31. #include <boost/cstdint.hpp> // for UINTMAX_C, boost::uintmax_t
  32. #include <boost/integer.hpp> // for boost::uint_t
  33. #include <boost/type_traits/conditional.hpp>
  34. #include <boost/type_traits/integral_constant.hpp>
  35. #include <boost/config/pragma_message.hpp>
  36. #include <climits> // for CHAR_BIT, etc.
  37. #include <cstddef> // for std::size_t
  38. #include <boost/limits.hpp> // for std::numeric_limits
  39. #if defined(BOOST_NO_CXX11_HDR_ARRAY) || \
  40. defined(BOOST_NO_CXX11_NOEXCEPT) // BOOST_NO_CXX11_HDR_TYPE_TRAITS is set for GCC 4.8
  41. BOOST_PRAGMA_MESSAGE("C++03 support is deprecated in Boost.CRC 1.84 and will be removed in Boost.CRC 1.86.")
  42. #endif
  43. // The type of CRC parameters that can go in a template should be related
  44. // on the CRC's bit count. This macro expresses that type in a compact
  45. // form, but also allows an alternate type for compilers that don't support
  46. // dependent types (in template value-parameters).
  47. #if !(defined(BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS))
  48. #define BOOST_CRC_PARM_TYPE typename ::boost::uint_t<Bits>::fast
  49. #else
  50. #define BOOST_CRC_PARM_TYPE unsigned long
  51. #endif
  52. namespace boost
  53. {
  54. // Forward declarations ----------------------------------------------------//
  55. //! Bit-wise CRC computer
  56. template < std::size_t Bits >
  57. class crc_basic;
  58. //! Table-driven CRC computer, usable as a function object
  59. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly = 0u,
  60. BOOST_CRC_PARM_TYPE InitRem = 0u,
  61. BOOST_CRC_PARM_TYPE FinalXor = 0u, bool ReflectIn = false,
  62. bool ReflectRem = false >
  63. class crc_optimal;
  64. //! Compute the (unaugmented) CRC of a memory block
  65. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  66. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  67. bool ReflectIn, bool ReflectRem >
  68. typename uint_t<Bits>::fast crc( void const *buffer,
  69. std::size_t byte_count);
  70. //! Compute the CRC of a memory block, with any augmentation provided by user
  71. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly >
  72. typename uint_t<Bits>::fast augmented_crc( void const *buffer,
  73. std::size_t byte_count,
  74. typename uint_t<Bits>::fast initial_remainder = 0u);
  75. //! Computation type for ARC|CRC-16|CRC-IBM|CRC-16/ARC|CRC-16/LHA standard
  76. typedef crc_optimal<16, 0x8005, 0, 0, true, true> crc_16_type;
  77. //! Computation type for CRC-16/CCITT-FALSE standard
  78. typedef crc_optimal<16, 0x1021, 0xFFFF, 0, false, false> crc_ccitt_false_t;
  79. //! Computation type for the CRC mistakenly called the CCITT standard
  80. typedef crc_ccitt_false_t crc_ccitt_type;
  81. //! Computation type for the actual
  82. //! KERMIT|CRC-16/CCITT|CRC-16/CCITT-TRUE|CRC-CCITT standard
  83. typedef crc_optimal<16, 0x1021, 0, 0, true, true> crc_ccitt_true_t;
  84. //! Computation type that I mistakenly called the XMODEM standard; it inverts
  85. //! both reflection parameters and reflects the truncated divisor (Don't use?!)
  86. typedef crc_optimal<16, 0x8408, 0, 0, true, true> crc_xmodem_type;
  87. //! Computation type for the actual XMODEM|ZMODEM|CRC-16/ACORN standard
  88. typedef crc_optimal<16, 0x1021, 0, 0, false, false> crc_xmodem_t;
  89. //! Computation type for CRC-32|CRC-32/ADCCP|PKZIP standard
  90. typedef crc_optimal<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true>
  91. crc_32_type;
  92. // Forward declarations for implementation detail stuff --------------------//
  93. // (Just for the stuff that will be needed for the next two sections)
  94. //! \cond
  95. namespace detail
  96. {
  97. //! Mix-in class to add a possibly-reflecting member function
  98. template < int BitLength, bool DoIt, int Id = 0 >
  99. class possible_reflector;
  100. //! Mix-in class for byte-fed, table-driven CRC algorithms
  101. template < int Order, boost::uintmax_t TruncatedPolynomial, bool Reflect,
  102. int Id = 0 >
  103. class crc_driver;
  104. } // namespace detail
  105. //! \endcond
  106. // Simple cyclic redundancy code (CRC) class declaration -------------------//
  107. /** Objects of this type compute the CRC checksum of submitted data, where said
  108. data can be entered piecemeal through several different kinds of groupings.
  109. Modulo-2 polynomial division steps are always performed bit-wise, without
  110. the use of pre-computation tables. Said division uses the altered
  111. algorithm, so any data has to be unaugmented.
  112. \pre 0 \< \a Bits \<= \c std\::numeric_limits\<uintmax_t\>\::digits
  113. \tparam Bits The order of the modulo-2 polynomial divisor. (\e Width from
  114. the RMCA)
  115. */
  116. template < std::size_t Bits >
  117. class crc_basic
  118. {
  119. public:
  120. // Type
  121. /** \brief The register type used for computations
  122. This type is used for CRC calculations and is the type for any returned
  123. checksums and returned or submitted remainders, (truncated) divisors, or
  124. XOR masks. It is a built-in unsigned integer type.
  125. */
  126. typedef typename boost::uint_t<Bits>::fast value_type;
  127. // Constant for the template parameter
  128. //! A copy of \a Bits provided for meta-programming purposes
  129. BOOST_STATIC_CONSTANT( std::size_t, bit_count = Bits );
  130. // Constructor (use the automatic copy-ctr, move-ctr, and dtr)
  131. //! Create a computer, separately listing each needed parameter
  132. explicit crc_basic( value_type truncated_polynomial,
  133. value_type initial_remainder = 0, value_type final_xor_value = 0,
  134. bool reflect_input = false, bool reflect_remainder = false );
  135. // Internal Operations
  136. //! Return the (truncated) polynomial divisor
  137. value_type get_truncated_polynominal() const;
  138. //! Return what the polynomial remainder was set to during construction
  139. value_type get_initial_remainder() const;
  140. //! Return the XOR-mask used during output processing
  141. value_type get_final_xor_value() const;
  142. //! Check if input-bytes will be reflected before processing
  143. bool get_reflect_input() const;
  144. //! Check if the remainder will be reflected during output processing
  145. bool get_reflect_remainder() const;
  146. //! Return the remainder based from already-processed bits
  147. value_type get_interim_remainder() const;
  148. //! Change the interim remainder to a new value
  149. void reset( value_type new_rem );
  150. //! Change the interim remainder back to the initial value
  151. void reset();
  152. // External Operations
  153. //! Submit a single bit for input processing
  154. void process_bit( bool bit );
  155. //! Submit the lowest \a bit_length bits of a byte for input processing
  156. void process_bits( unsigned char bits, std::size_t bit_length );
  157. //! Submit a single byte for input processing
  158. void process_byte( unsigned char byte );
  159. //! Submit a memory block for input processing, iterator-pair style
  160. void process_block( void const *bytes_begin, void const *bytes_end );
  161. //! Submit a memory block for input processing, pointer-and-size style
  162. void process_bytes( void const *buffer, std::size_t byte_count );
  163. //! Return the checksum of the already-processed bits
  164. value_type checksum() const;
  165. private:
  166. // Member data
  167. value_type rem_;
  168. value_type poly_, init_, final_; // non-const to allow assignability
  169. bool rft_in_, rft_out_; // non-const to allow assignability
  170. }; // boost::crc_basic
  171. // Optimized cyclic redundancy code (CRC) class declaration ----------------//
  172. /** Objects of this type compute the CRC checksum of submitted data, where said
  173. data can be entered piecemeal through several different kinds of groupings.
  174. Modulo-2 polynomial division steps are performed byte-wise, aided by the use
  175. of pre-computation tables. Said division uses the altered algorithm, so any
  176. data has to be unaugmented.
  177. \pre 0 \< \a Bits \<= \c std\::numeric_limits\<uintmax_t\>\::digits
  178. \tparam Bits The order of the modulo-2 polynomial divisor. (\e Width from
  179. the RMCA)
  180. \tparam TruncPoly The lowest coefficients of the divisor polynomial. The
  181. highest-order coefficient is omitted and always assumed to be 1. Defaults
  182. to \c 0, i.e. the only non-zero term is the implicit one for
  183. x<sup><var>Bits</var></sup>. (\e Poly from the RMCA)
  184. \tparam InitRem The (unaugmented) initial state of the polynomial
  185. remainder. Defaults to \c 0 if omitted. (\e Init from the RMCA)
  186. \tparam FinalXor The (XOR) bit-mask to be applied to the output remainder,
  187. after possible reflection but before returning. Defaults to \c 0 (i.e. no
  188. bit changes) if omitted. (\e XorOut from the RMCA)
  189. \tparam ReflectIn If \c true, input bytes are read lowest-order bit first,
  190. otherwise highest-order bit first. Defaults to \c false if omitted.
  191. (\e RefIn from the RMCA)
  192. \tparam ReflectRem If \c true, the output remainder is reflected before the
  193. XOR-mask. Defaults to \c false if omitted. (\e RefOut from the RMCA)
  194. \todo Get rid of the default value for \a TruncPoly. Choosing a divisor is
  195. an important decision with many factors, so a default is never useful,
  196. especially a bad one.
  197. */
  198. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  199. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  200. bool ReflectIn, bool ReflectRem >
  201. class crc_optimal
  202. {
  203. public:
  204. // Type
  205. //! \copydoc boost::crc_basic::value_type
  206. typedef typename boost::uint_t<Bits>::fast value_type;
  207. // Constants for the template parameters
  208. //! \copydoc boost::crc_basic::bit_count
  209. BOOST_STATIC_CONSTANT( std::size_t, bit_count = Bits );
  210. //! A copy of \a TruncPoly provided for meta-programming purposes
  211. BOOST_STATIC_CONSTANT( value_type, truncated_polynominal = TruncPoly );
  212. //! A copy of \a InitRem provided for meta-programming purposes
  213. BOOST_STATIC_CONSTANT( value_type, initial_remainder = InitRem );
  214. //! A copy of \a FinalXor provided for meta-programming purposes
  215. BOOST_STATIC_CONSTANT( value_type, final_xor_value = FinalXor );
  216. //! A copy of \a ReflectIn provided for meta-programming purposes
  217. BOOST_STATIC_CONSTANT( bool, reflect_input = ReflectIn );
  218. //! A copy of \a ReflectRem provided for meta-programming purposes
  219. BOOST_STATIC_CONSTANT( bool, reflect_remainder = ReflectRem );
  220. // Constructor (use the automatic copy-ctr, move-ctr, and dtr)
  221. //! Create a computer, giving an initial remainder if desired
  222. explicit crc_optimal( value_type init_rem = initial_remainder );
  223. // Internal Operations
  224. //! \copybrief boost::crc_basic::get_truncated_polynominal
  225. value_type get_truncated_polynominal() const;
  226. //! \copybrief boost::crc_basic::get_initial_remainder
  227. value_type get_initial_remainder() const;
  228. //! \copybrief boost::crc_basic::get_final_xor_value
  229. value_type get_final_xor_value() const;
  230. //! \copybrief boost::crc_basic::get_reflect_input
  231. bool get_reflect_input() const;
  232. //! \copybrief boost::crc_basic::get_reflect_remainder
  233. bool get_reflect_remainder() const;
  234. //! \copybrief boost::crc_basic::get_interim_remainder
  235. value_type get_interim_remainder() const;
  236. //! Change the interim remainder to either a given value or the initial one
  237. void reset( value_type new_rem = initial_remainder );
  238. // External Operations
  239. //! \copybrief boost::crc_basic::process_byte
  240. void process_byte( unsigned char byte );
  241. //! \copybrief boost::crc_basic::process_block
  242. void process_block( void const *bytes_begin, void const *bytes_end );
  243. //! \copybrief boost::crc_basic::process_bytes
  244. void process_bytes( void const *buffer, std::size_t byte_count );
  245. //! \copybrief boost::crc_basic::checksum
  246. value_type checksum() const;
  247. // Operators
  248. //! Submit a single byte for input processing, suitable for the STL
  249. void operator ()( unsigned char byte );
  250. //! Return the checksum of the already-processed bits, suitable for the STL
  251. value_type operator ()() const;
  252. private:
  253. // Implementation types
  254. // (Processing for reflected input gives reflected remainders, so you only
  255. // have to apply output-reflection if Reflect-Remainder doesn't match
  256. // Reflect-Input.)
  257. typedef detail::possible_reflector<Bits, ReflectIn> reflect_i_type;
  258. typedef detail::crc_driver<Bits, TruncPoly, ReflectIn> crc_table_type;
  259. typedef detail::possible_reflector<Bits, ReflectRem != ReflectIn>
  260. reflect_o_type;
  261. // Member data
  262. value_type rem_;
  263. }; // boost::crc_optimal
  264. // Implementation detail stuff ---------------------------------------------//
  265. //! \cond
  266. namespace detail
  267. {
  268. /** \brief Meta-programming integral constant for a single-bit bit-mask
  269. Generates a compile-time constant for a bit-mask that affects a single
  270. bit. The \c value will be 2<sup><var>BitIndex</var></sup>. The \c type
  271. will be the smallest built-in unsigned integer type that can contain the
  272. value, unless there's a built-in type that the system can handle easier,
  273. then the \c type will be smallest fast-handled unsigned integer type.
  274. \pre 0 \<= BitIndex \< \c std\::numeric_limits\<uintmax_t\>\::digits
  275. \tparam BitIndex The place of the sole set bit.
  276. */
  277. template < int BitIndex >
  278. struct high_bit_mask_c
  279. : boost::integral_constant<typename boost::uint_t< BitIndex + 1 >::fast,
  280. ( UINTMAX_C(1) << BitIndex )>
  281. {};
  282. /** \brief Meta-programming integral constant for a lowest-bits bit-mask
  283. Generates a compile-time constant for a bit-mask that affects the lowest
  284. bits. The \c value will be 2<sup><var>BitCount</var></sup> - 1. The
  285. \c type will be the smallest built-in unsigned integer type that can
  286. contain the value, unless there's a built-in type that the system can
  287. handle easier, then the \c type will be smallest fast-handled unsigned
  288. integer type.
  289. \pre 0 \<= BitCount \<= \c std\::numeric_limits\<uintmax_t\>\::digits
  290. \tparam BitCount The number of lowest-placed bits set.
  291. */
  292. template < int BitCount >
  293. struct low_bits_mask_c
  294. : boost::integral_constant<typename boost::uint_t< BitCount >::fast, (
  295. BitCount ? (( (( UINTMAX_C(1) << (BitCount - 1) ) - 1u) << 1 ) |
  296. UINTMAX_C( 1 )) : 0u )>
  297. {};
  298. /** \brief Reflects the bits of a number
  299. Reverses the order of the given number of bits within a value. For
  300. instance, if the given reflect count is 5, then the bit values for the
  301. 16- and 1-place will switch and the 8- and 2-place will switch, leaving
  302. the other bits alone. (The 4-place bit is in the middle, so it wouldn't
  303. change.)
  304. \pre \a Unsigned is a built-in unsigned integer type
  305. \pre 0 \< word_length \<= \c std\::numeric_limits\<Unsigned\>\::digits
  306. \tparam Unsigned The type of \a x.
  307. \param x The value to be (partially) reflected.
  308. \param word_length The number of low-order bits to reflect. Defaults
  309. to the total number of value bits in \a Unsigned.
  310. \return The (partially) reflected value.
  311. \todo Check if this is the fastest way.
  312. */
  313. template < typename Unsigned >
  314. Unsigned reflect_unsigned( Unsigned x, int word_length
  315. = std::numeric_limits<Unsigned>::digits )
  316. {
  317. for ( Unsigned l = 1u, h = static_cast<Unsigned>(l << (word_length - 1)) ; h > l ; h >>= 1, l
  318. <<= 1 )
  319. {
  320. Unsigned const m = h | l, t = x & m;
  321. if ( (t == h) || (t == l) )
  322. x ^= m;
  323. }
  324. return x;
  325. }
  326. /** \brief Make a byte-to-byte-reflection map
  327. Creates a mapping array so the results can be cached. Uses
  328. #reflect_unsigned to generate the element values.
  329. \return An array <var>a</var> such that, for a given byte value
  330. <var>i</var>, <code><var>a</var>[ <var>i</var> ]</code> resolves to
  331. the reflected value of <var>i</var>.
  332. */
  333. boost::array< unsigned char, (UINTMAX_C( 1 ) << CHAR_BIT) >
  334. inline make_byte_reflection_table()
  335. {
  336. boost::array<unsigned char, ( UINTMAX_C(1) << CHAR_BIT )> result;
  337. unsigned char i = 0u;
  338. do
  339. result[ i ] = reflect_unsigned( i );
  340. while ( ++i );
  341. return result;
  342. }
  343. /** \brief Reflects the bits of a single byte
  344. Reverses the order of all the bits within a value. For instance, the
  345. bit values for the 2<sup><code>CHAR_BIT</code> - 1</sup>- and 1-place
  346. will switch and the 2<sup><code>CHAR_BIT</code> - 2</sup>- and 2-place
  347. will switch, etc.
  348. \param x The byte value to be reflected.
  349. \return The reflected value.
  350. \note Since this could be the most common type of reflection, and the
  351. number of states is relatively small, the implementation pre-computes
  352. and uses a table of all the results.
  353. */
  354. inline unsigned char reflect_byte( unsigned char x )
  355. {
  356. static boost::array<unsigned char, ( UINTMAX_C(1) << CHAR_BIT )> const
  357. table = make_byte_reflection_table();
  358. return table[ x ];
  359. }
  360. /** \brief Reflects some bits within a single byte
  361. Like #reflect_unsigned, except it takes advantage of any (long-term)
  362. speed gains #reflect_byte may bring.
  363. \pre 0 \< \a word_length \<= \c CHAR_BIT
  364. \param x The value to be (partially) reflected.
  365. \param word_length The number of low-order bits to reflect.
  366. \return The (partially) reflected value.
  367. */
  368. inline unsigned char reflect_sub_byte( unsigned char x, int word_length )
  369. { return reflect_byte(x) >> (CHAR_BIT - word_length); }
  370. /** \brief Possibly reflects the bits of a number
  371. Reverses the order of the given number of bits within a value. For
  372. instance, if the given reflect count is 5, then the bit values for the
  373. 16- and 1-place will switch and the 8- and 2-place will switch, leaving
  374. the other bits alone. (The 4-place bit is in the middle, so it wouldn't
  375. change.) This variant function allows the reflection be controlled by
  376. an extra parameter, in case the decision to use reflection is made at
  377. run-time.
  378. \pre \a Unsigned is a built-in unsigned integer type
  379. \pre 0 \< word_length \<= \c std\::numeric_limits\<Unsigned\>\::digits
  380. \tparam Unsigned The type of \a x.
  381. \param x The value to be (partially) reflected.
  382. \param reflect Controls whether \a x is actually reflected (\c true) or
  383. left alone (\c false).
  384. \param word_length The number of low-order bits to reflect. Defaults
  385. to the total number of value bits in \a Unsigned.
  386. \return The possibly (partially) reflected value.
  387. */
  388. template < typename Unsigned >
  389. inline
  390. Unsigned reflect_optionally( Unsigned x, bool reflect, int word_length
  391. = std::numeric_limits<Unsigned>::digits )
  392. { return reflect ? reflect_unsigned(x, word_length) : x; }
  393. /** \brief Possibly reflects the bits of a single byte
  394. Uses #reflect_byte (if \a reflect is \c true).
  395. \param x The byte value to be (possibly) reflected.
  396. \param reflect Whether (\c true) or not (\c false) \a x is reflected.
  397. \return <code><var>reflect</var> ? reflect_byte(<var>x</var>) :
  398. <var>x</var></code>
  399. */
  400. inline
  401. unsigned char reflect_byte_optionally( unsigned char x, bool reflect )
  402. { return reflect ? reflect_byte(x) : x; }
  403. /** \brief Update a CRC remainder by several bits, assuming a non-augmented
  404. message
  405. Performs several steps of division required by the CRC algorithm, giving
  406. a new remainder polynomial based on the divisor polynomial and the
  407. synthesized dividend polynomial (from the old remainder and the
  408. newly-provided input). The computations assume that the CRC is directly
  409. exposed from the remainder, without any zero-valued bits augmented to
  410. the message bits.
  411. \pre \a Register and \a Word are both built-in unsigned integer types
  412. \pre 0 \< \a register_length \<= std\::numeric_limits\<\a Register\>
  413. \::digits
  414. \pre 0 \< \a word_length \<= std\::numeric_limits\<\a Word\>\::digits
  415. \tparam Register The type used for representing the remainder and
  416. divisor modulo-2 polynomials. The bit at <code>2<sup>i</sup></code>
  417. is used as the coefficient of <i>x<sup>i</sup></i>.
  418. \tparam Word The type used for storing the incoming terms of the
  419. dividend modulo-2 polynomial. The bit at <code>2<sup>i</sup></code>
  420. is used as the coefficient of <i>x<sup>i</sup></i> when \a reflect is
  421. \c false, and the coefficient of <i>x<sup><var>word_length</var> - 1 -
  422. i</sup></i> otherwise.
  423. \param[in] register_length The number of significant low-order bits
  424. to be used from \a Register values. It is the order of the modulo-2
  425. polynomial remainder and one less than the divisor's order.
  426. \param[in,out] remainder The upper part of the dividend polynomial
  427. before division, and the remainder polynomial after.
  428. \param[in] new_dividend_bits The coefficients for the next
  429. \a word_length lowest terms of the dividend polynomial.
  430. \param[in] truncated_divisor The lowest coefficients of the divisor
  431. polynomial. The highest-order coefficient is omitted and always
  432. assumed to be 1.
  433. \param[in] word_length The number of lowest-order bits to read from
  434. \a new_dividend_bits.
  435. \param[in] reflect If \c false, read from the highest-order marked
  436. bit from \a new_dividend_bits and go down, as normal. Otherwise,
  437. proceed from the lowest-order bit and go up.
  438. \note This routine performs a modulo-2 polynomial division variant.
  439. The exclusive-or operations are applied in a different order, since
  440. that kind of operation is commutative and associative. It also
  441. assumes that the zero-valued augment string was applied before this
  442. step, which means that the updated remainder can be directly used as
  443. the final CRC.
  444. */
  445. template < typename Register, typename Word >
  446. void crc_modulo_word_update( int register_length, Register &remainder, Word
  447. new_dividend_bits, Register truncated_divisor, int word_length, bool
  448. reflect )
  449. {
  450. // Create this masking constant outside the loop.
  451. Register const high_bit_mask = UINTMAX_C(1) << (register_length - 1);
  452. // The natural reading order for division is highest digit/bit first.
  453. // The "reflect" parameter switches this. However, building a bit mask
  454. // for the lowest bit is the easiest....
  455. new_dividend_bits = reflect_optionally( new_dividend_bits, !reflect,
  456. word_length );
  457. // Perform modulo-2 division for each new dividend input bit
  458. for ( int i = word_length ; i ; --i, new_dividend_bits >>= 1 )
  459. {
  460. // compare the new bit with the remainder's highest
  461. remainder ^= ( new_dividend_bits & 1u ) ? high_bit_mask : 0u;
  462. // perform modulo-2 division
  463. bool const quotient = (remainder & high_bit_mask) != 0;
  464. remainder <<= 1;
  465. remainder ^= quotient ? truncated_divisor : 0u;
  466. // The quotient isn't used for anything, so don't keep it.
  467. }
  468. // Clear overflowed bits
  469. remainder &= std::numeric_limits<Register>::max() >> (std::numeric_limits<Register>::digits - register_length);
  470. }
  471. /** \brief Update a CRC remainder by a single bit, assuming a non-augmented
  472. message
  473. Performs the next step of division required by the CRC algorithm, giving
  474. a new remainder polynomial based on the divisor polynomial and the
  475. synthesized dividend polynomial (from the old remainder and the
  476. newly-provided input). The computations assume that the CRC is directly
  477. exposed from the remainder, without any zero-valued bits augmented to
  478. the message bits.
  479. \pre \a Register is a built-in unsigned integer type
  480. \pre 0 \< \a register_length \<= std\::numeric_limits\<\a Register\>
  481. \::digits
  482. \tparam Register The type used for representing the remainder and
  483. divisor modulo-2 polynomials. The bit at <code>2<sup>i</sup></code>
  484. is used as the coefficient of <i>x<sup>i</sup></i>.
  485. \param[in] register_length The number of significant low-order bits
  486. to be used from \a Register values. It is the order of the modulo-2
  487. polynomial remainder and one less than the divisor's order.
  488. \param[in,out] remainder The upper part of the dividend polynomial
  489. before division, and the remainder polynomial after.
  490. \param[in] new_dividend_bit The coefficient for the constant term
  491. of the dividend polynomial.
  492. \param[in] truncated_divisor The lowest coefficients of the divisor
  493. polynomial. The highest-order coefficient is omitted and always
  494. assumed to be 1.
  495. \note This routine performs a modulo-2 polynomial division variant.
  496. The exclusive-or operations are applied in a different order, since
  497. that kind of operation is commutative and associative. It also
  498. assumes that the zero-valued augment string was applied before this
  499. step, which means that the updated remainder can be directly used as
  500. the final CRC.
  501. */
  502. template < typename Register >
  503. inline void crc_modulo_update( int register_length, Register &remainder,
  504. bool new_dividend_bit, Register truncated_divisor )
  505. {
  506. crc_modulo_word_update( register_length, remainder,
  507. static_cast<unsigned>(new_dividend_bit), truncated_divisor, 1, false );
  508. }
  509. /** \brief Update a CRC remainder by several bits, assuming an augmented
  510. message
  511. Performs several steps of division required by the CRC algorithm, giving
  512. a new remainder polynomial based on the divisor polynomial and the
  513. synthesized dividend polynomial (from the old remainder and the
  514. newly-provided input). The computations assume that a zero-valued
  515. string of bits will be appended to the message before extracting the
  516. CRC.
  517. \pre \a Register and \a Word are both built-in unsigned integer types
  518. \pre 0 \< \a register_length \<= std\::numeric_limits\<\a Register\>
  519. \::digits
  520. \pre 0 \< \a word_length \<= std\::numeric_limits\<\a Word\>\::digits
  521. \tparam Register The type used for representing the remainder and
  522. divisor modulo-2 polynomials. The bit at <code>2<sup>i</sup></code>
  523. is used as the coefficient of <i>x<sup>i</sup></i>.
  524. \tparam Word The type used for storing the incoming terms of the
  525. dividend modulo-2 polynomial. The bit at <code>2<sup>i</sup></code>
  526. is used as the coefficient of <i>x<sup>i</sup></i> when \a reflect is
  527. \c false, and the coefficient of <i>x<sup><var>word_length</var> - 1 -
  528. i</sup></i> otherwise.
  529. \param[in] register_length The number of significant low-order bits
  530. to be used from \a Register values. It is the order of the modulo-2
  531. polynomial remainder and one less than the divisor's order.
  532. \param[in,out] remainder The upper part of the dividend polynomial
  533. before division, and the remainder polynomial after.
  534. \param[in] new_dividend_bits The coefficients for the next
  535. \a word_length lowest terms of the dividend polynomial.
  536. \param[in] truncated_divisor The lowest coefficients of the divisor
  537. polynomial. The highest-order coefficient is omitted and always
  538. assumed to be 1.
  539. \param[in] word_length The number of lowest-order bits to read from
  540. \a new_dividend_bits.
  541. \param[in] reflect If \c false, read from the highest-order marked
  542. bit from \a new_dividend_bits and go down, as normal. Otherwise,
  543. proceed from the lowest-order bit and go up.
  544. \note This routine performs straight-forward modulo-2 polynomial
  545. division. It assumes that an augment string will be processed at the
  546. end of the message bits before doing CRC analysis.
  547. \todo Use this function somewhere so I can test it.
  548. */
  549. template < typename Register, typename Word >
  550. void augmented_crc_modulo_word_update( int register_length, Register
  551. &remainder, Word new_dividend_bits, Register truncated_divisor, int
  552. word_length, bool reflect )
  553. {
  554. // Create this masking constant outside the loop.
  555. Register const high_bit_mask = UINTMAX_C(1) << (register_length - 1);
  556. // The natural reading order for division is highest digit/bit first.
  557. // The "reflect" parameter switches this. However, building a bit mask
  558. // for the lowest bit is the easiest....
  559. new_dividend_bits = reflect_optionally( new_dividend_bits, !reflect,
  560. word_length );
  561. // Perform modulo-2 division for each new dividend input bit
  562. for ( int i = word_length ; i ; --i, new_dividend_bits >>= 1 )
  563. {
  564. bool const quotient = (remainder & high_bit_mask) != 0;
  565. remainder <<= 1;
  566. remainder |= new_dividend_bits & 1u;
  567. remainder ^= quotient ? truncated_divisor : 0u;
  568. // The quotient isn't used for anything, so don't keep it.
  569. }
  570. }
  571. /** \brief Update a CRC remainder by a single bit, assuming an augmented
  572. message
  573. Performs the next step of division required by the CRC algorithm, giving
  574. a new remainder polynomial based on the divisor polynomial and the
  575. synthesized dividend polynomial (from the old remainder and the
  576. newly-provided input). The computations assume that a zero-valued
  577. string of bits will be appended to the message before extracting the
  578. CRC.
  579. \pre \a Register is a built-in unsigned integer type
  580. \pre 0 \< \a register_length \<= std\::numeric_limits\<\a Register\>
  581. \::digits
  582. \tparam Register The type used for representing the remainder and
  583. divisor modulo-2 polynomials. The bit at <code>2<sup>i</sup></code>
  584. is used as the coefficient of <i>x<sup>i</sup></i>.
  585. \param[in] register_length The number of significant low-order bits
  586. to be used from \a Register values. It is the order of the modulo-2
  587. polynomial remainder and one less than the divisor's order.
  588. \param[in,out] remainder The upper part of the dividend polynomial
  589. before division, and the remainder polynomial after.
  590. \param[in] new_dividend_bit The coefficient for the constant term
  591. of the dividend polynomial.
  592. \param[in] truncated_divisor The lowest coefficients of the divisor
  593. polynomial. The highest-order coefficient is omitted and always
  594. assumed to be 1.
  595. \note This routine performs straight-forward modulo-2 polynomial
  596. division. It assumes that an augment string will be processed at the
  597. end of the message bits before doing CRC analysis.
  598. \todo Use this function somewhere so I can test it.
  599. */
  600. template < typename Register >
  601. inline void augmented_crc_modulo_update( int register_length, Register
  602. &remainder, bool new_dividend_bit, Register truncated_divisor )
  603. {
  604. augmented_crc_modulo_word_update( register_length, remainder,
  605. static_cast<unsigned>(new_dividend_bit), truncated_divisor, 1, false );
  606. }
  607. /** \brief A mix-in class that returns its argument
  608. This class template makes a function object that returns its argument
  609. as-is. It's one case for #possible_reflector.
  610. \pre 0 \< \a BitLength \<= \c std\::numeric_limits\<uintmax_t\>
  611. \::digits
  612. \tparam BitLength How many significant bits arguments have.
  613. */
  614. template < int BitLength >
  615. class non_reflector
  616. {
  617. public:
  618. /** \brief The type to check for specialization
  619. This is a Boost integral constant indicating that this class
  620. does not reflect its input values.
  621. */
  622. typedef boost::false_type is_reflecting_type;
  623. /** \brief The type to check for register bit length
  624. This is a Boost integral constant indicating how many
  625. significant bits won't actually be reflected.
  626. */
  627. typedef boost::integral_constant< int, BitLength > width_c;
  628. /** \brief The type of (not-)reflected values
  629. This type is the input and output type for the (possible-)
  630. reflection function, which does nothing here.
  631. */
  632. typedef typename boost::uint_t< BitLength >::fast value_type;
  633. /** \brief Does nothing
  634. Returns the given value, not reflecting any part of it.
  635. \param x The value to not be reflected.
  636. \return \a x
  637. */
  638. inline static value_type reflect_q( value_type x )
  639. { return x; }
  640. };
  641. /** \brief A mix-in class that reflects (the lower part of) its argument,
  642. generally for types larger than a byte
  643. This class template makes a function object that returns its argument
  644. after reflecting its lower-order bits. It's one sub-case for
  645. #possible_reflector.
  646. \pre \c CHAR_BIT \< \a BitLength \<= \c std\::numeric_limits\<uintmax_t
  647. \>\::digits
  648. \tparam BitLength How many significant bits arguments have.
  649. */
  650. template < int BitLength >
  651. class super_byte_reflector
  652. {
  653. public:
  654. /** \brief The type to check for specialization
  655. This is a Boost integral constant indicating that this class
  656. does reflect its input values.
  657. */
  658. typedef boost::true_type is_reflecting_type;
  659. /** \brief The type to check for register bit length
  660. This is a Boost integral constant indicating how many
  661. significant bits will be reflected.
  662. */
  663. typedef boost::integral_constant< int, BitLength > width_c;
  664. /** \brief The type of reflected values
  665. This is both the input and output type for the reflection function.
  666. */
  667. typedef typename boost::uint_t< BitLength >::fast value_type;
  668. /** \brief Reflect (part of) the given value
  669. Reverses the order of the given number of bits within a value,
  670. using #reflect_unsigned.
  671. \param x The value to be (partially) reflected.
  672. \return ( <var>x</var> &amp;
  673. ~(2<sup><var>width_c</var>\::value</sup> - 1) ) | REFLECT(
  674. <var>x</var> &amp; (2<sup><var>width_c</var>\::value</sup> -
  675. 1) )
  676. */
  677. inline static value_type reflect_q( value_type x )
  678. { return reflect_unsigned(x, width_c::value); }
  679. };
  680. /** \brief A mix-in class that reflects (the lower part of) its argument,
  681. generally for bytes
  682. This class template makes a function object that returns its argument
  683. after reflecting its lower-order bits. It's one sub-case for
  684. #possible_reflector.
  685. \pre 0 \< \a BitLength \<= \c CHAR_BIT
  686. \tparam BitLength How many significant bits arguments have.
  687. */
  688. template < int BitLength >
  689. class sub_type_reflector
  690. {
  691. public:
  692. /** \brief The type to check for specialization
  693. This is a Boost integral constant indicating that this class
  694. does reflect its input values.
  695. */
  696. typedef boost::true_type is_reflecting_type;
  697. /** \brief The type to check for register bit length
  698. This is a Boost integral constant indicating how many
  699. significant bits will be reflected.
  700. */
  701. typedef boost::integral_constant< int, BitLength > width_c;
  702. /** \brief The type of reflected values
  703. This is both the input and output type for the reflection function.
  704. */
  705. typedef unsigned char value_type;
  706. /** \brief Reflect (part of) the given value
  707. Reverses the order of the given number of bits within a value,
  708. using #reflect_sub_byte.
  709. \param x The value to be (partially) reflected.
  710. \return ( <var>x</var> &amp;
  711. ~(2<sup><var>width_c</var>\::value</sup> - 1) ) | REFLECT(
  712. <var>x</var> &amp; (2<sup><var>width_c</var>\::value</sup> -
  713. 1) )
  714. */
  715. inline static value_type reflect_q( value_type x )
  716. { return reflect_sub_byte(x, width_c::value); }
  717. };
  718. /** \brief A mix-in class that reflects (the lower part of) its argument
  719. This class template makes a function object that returns its argument
  720. after reflecting its lower-order bits. It's one case for
  721. #possible_reflector.
  722. \pre 0 \< \a BitLength \<= \c std\::numeric_limits\<uintmax_t\>
  723. \::digits
  724. \tparam BitLength How many significant bits arguments have.
  725. */
  726. template < int BitLength >
  727. class reflector
  728. : public boost::conditional< (BitLength > CHAR_BIT),
  729. super_byte_reflector<BitLength>, sub_type_reflector<BitLength> >::type
  730. { };
  731. /** This class template adds a member function #reflect_q that will
  732. conditionally reflect its first argument, controlled by a compile-time
  733. parameter.
  734. \pre 0 \< \a BitLength \<= \c std\::numeric_limits\<uintmax_t\>
  735. \::digits
  736. \tparam BitLength How many significant bits arguments have.
  737. \tparam DoIt \c true if #reflect_q will reflect, \c false if it should
  738. return its argument unchanged.
  739. \tparam Id An extra differentiator if multiple copies of this class
  740. template are mixed-in as base classes. Defaults to 0 if omitted.
  741. */
  742. template < int BitLength, bool DoIt, int Id >
  743. class possible_reflector
  744. : public boost::conditional< DoIt, reflector<BitLength>,
  745. non_reflector<BitLength> >::type
  746. {
  747. public:
  748. /** \brief The type to check for ID
  749. This is a Boost integral constant indicating what ID number this
  750. instantiation used.
  751. */
  752. typedef boost::integral_constant<int, Id> id_type;
  753. };
  754. /** \brief Find the composite remainder update effect from a fixed bit
  755. sequence, for each potential sequence combination.
  756. For each value between 0 and 2<sup><var>SubOrder</var></sup> - 1,
  757. computes the XOR mask corresponding to the composite effect they update
  758. the incoming remainder, which is the upper part of the dividend that
  759. gets (partially) pushed out of its register by the incoming value's
  760. bits. The composite value merges the \"partial products\" from each bit
  761. of the value being updated individually.
  762. \pre \a Register is a built-in unsigned integer type
  763. \pre 0 \< \a SubOrder \<= \a register_length \<=
  764. std\::numeric_limits\<\a Register\>\::digits
  765. \tparam SubOrder The number of low-order significant bits of the trial
  766. new dividends.
  767. \tparam Register The type used for representing the remainder and
  768. divisor modulo-2 polynomials. The bit at <code>2<sup>i</sup></code>
  769. is used as the coefficient of <i>x<sup>i</sup></i>.
  770. \param[in] register_length The number of significant low-order bits
  771. to be used from \a Register values. It is the order of the modulo-2
  772. polynomial remainder and one less than the divisor's order.
  773. \param[in] truncated_divisor The lowest coefficients of the divisor
  774. polynomial. The highest-order coefficient is omitted and always
  775. assumed to be 1.
  776. \param[in] reflect If \c false, read from the highest-order marked
  777. bit from a new dividend's bits and go down, as normal. Otherwise,
  778. proceed from the lowest-order bit and go up.
  779. \return An array such that the element at index <var>i</var> is the
  780. composite effect XOR mask for value <var>i</var>.
  781. \note This routine performs a modulo-2 polynomial division variant.
  782. The exclusive-or operations are applied in a different order, since
  783. that kind of operation is commutative and associative. It also
  784. assumes that the zero-valued augment string was applied before this
  785. step, which means that the updated remainder can be directly used as
  786. the final CRC.
  787. \todo Check that using the unaugmented-CRC division routines give the
  788. same composite mask table as using augmented-CRC routines.
  789. */
  790. template < int SubOrder, typename Register >
  791. boost::array< Register, (UINTMAX_C( 1 ) << SubOrder) >
  792. make_partial_xor_products_table( int register_length, Register
  793. truncated_divisor, bool reflect )
  794. {
  795. boost::array<Register, ( UINTMAX_C(1) << SubOrder )> result = { 0 };
  796. // Loop over every possible dividend value
  797. for ( typename boost::uint_t<SubOrder + 1>::fast dividend = 0u;
  798. dividend < result.size() ; ++dividend )
  799. {
  800. Register remainder = 0u;
  801. crc_modulo_word_update( register_length, remainder, dividend,
  802. truncated_divisor, SubOrder, false );
  803. result[ reflect_optionally(dividend, reflect, SubOrder) ] =
  804. reflect_optionally( remainder, reflect, register_length );
  805. }
  806. return result;
  807. }
  808. /** \brief A mix-in class for the table of table-driven CRC algorithms
  809. Encapsulates the parameters need to make a global (technically,
  810. class-static) table usuable in CRC algorithms, and generates said
  811. table.
  812. \pre 0 \< \a SubOrder \<= Order \<=
  813. std\::numeric_limits\<uintmax_t\>\::digits
  814. \tparam Order The order of the modulo-2 polynomial remainder and one
  815. less than the divisor's order.
  816. \tparam SubOrder The number of low-order significant bits of the trial
  817. new dividends.
  818. \tparam TruncatedPolynomial The lowest coefficients of the divisor
  819. polynomial. The highest-order coefficient is omitted and always
  820. assumed to be 1.
  821. \tparam Reflect If \c false, read from the highest-order marked
  822. bit from a new dividend's bits and go down, as normal. Otherwise,
  823. proceed from the lowest-order bit and go up.
  824. */
  825. template < int Order, int SubOrder, boost::uintmax_t TruncatedPolynomial,
  826. bool Reflect >
  827. class crc_table_t
  828. {
  829. public:
  830. /** \brief The type to check for register bit length
  831. This is a Boost integral constant indicating how many
  832. significant bits are in the remainder and (truncated) divisor.
  833. */
  834. typedef boost::integral_constant< int, Order > width_c;
  835. /** \brief The type to check for index-unit bit length
  836. This is a Boost integral constant indicating how many
  837. significant bits are in the trial new dividends.
  838. */
  839. typedef boost::integral_constant< int, SubOrder > unit_width_c;
  840. /** \brief The type of registers
  841. This is the output type for the partial-product map.
  842. */
  843. typedef typename boost::uint_t< Order >::fast value_type;
  844. /** \brief The type to check the divisor
  845. This is a Boost integral constant representing the (truncated)
  846. divisor.
  847. */
  848. typedef boost::integral_constant< value_type, TruncatedPolynomial >
  849. poly_c;
  850. /** \brief The type to check for reflection
  851. This is a Boost integral constant representing whether input
  852. units should be read in reverse order.
  853. */
  854. typedef boost::integral_constant< bool, Reflect > refin_c;
  855. /** \brief The type to check for map size
  856. This is a Boost integral constant representing the number of
  857. elements in the partial-product map, based on the unit size.
  858. */
  859. typedef high_bit_mask_c< SubOrder > table_size_c;
  860. /** \brief The type of the unit TO partial-product map
  861. This is the array type that takes units as the index and said unit's
  862. composite partial-product mask as the element.
  863. */
  864. typedef boost::array<value_type, table_size_c::value> array_type;
  865. /** \brief Create a global array for the mapping table
  866. Creates an instance of a partial-product array with this class's
  867. parameters.
  868. \return A reference to a immutable array giving the partial-product
  869. update XOR map for each potential sub-unit value.
  870. */
  871. static array_type const & get_table()
  872. {
  873. static array_type const table =
  874. make_partial_xor_products_table<unit_width_c::value>(
  875. width_c::value, poly_c::value, refin_c::value );
  876. return table;
  877. }
  878. };
  879. /** \brief A mix-in class that handles direct (i.e. non-reflected) byte-fed
  880. table-driven CRC algorithms
  881. This class template adds member functions #augmented_crc_update and
  882. #crc_update to update remainders from new input bytes. The bytes aren't
  883. reflected before processing.
  884. \pre \c CHAR_BIT \<= \a Order \<= \c std\::numeric_limits\<uintmax_t\>
  885. \::digits
  886. \tparam Order The order of the modulo-2 polynomial remainder and one
  887. less than the divisor's order.
  888. \tparam TruncatedPolynomial The lowest coefficients of the divisor
  889. polynomial. The highest-order coefficient is omitted and always
  890. assumed to be 1.
  891. */
  892. template < int Order, boost::uintmax_t TruncatedPolynomial >
  893. class direct_byte_table_driven_crcs
  894. : public crc_table_t<Order, CHAR_BIT, TruncatedPolynomial, false>
  895. {
  896. typedef crc_table_t<Order, CHAR_BIT, TruncatedPolynomial, false>
  897. base_type;
  898. public:
  899. typedef typename base_type::value_type value_type;
  900. typedef typename base_type::array_type array_type;
  901. /** \brief Compute the updated remainder after reading some bytes
  902. The implementation reads from a table to speed-up applying
  903. augmented-CRC updates byte-wise.
  904. \param remainder The pre-update remainder
  905. \param new_dividend_bytes The address where the new bytes start
  906. \param new_dividend_byte_count The number of new bytes to read
  907. \return The updated remainder
  908. */
  909. static value_type augmented_crc_update( value_type remainder, unsigned
  910. char const *new_dividend_bytes, std::size_t new_dividend_byte_count)
  911. {
  912. static array_type const & table = base_type::get_table();
  913. while ( new_dividend_byte_count-- )
  914. {
  915. // Locates the merged partial product based on the leading byte
  916. unsigned char const index = ( remainder >> (Order - CHAR_BIT) )
  917. & UCHAR_MAX;
  918. // Complete the multi-bit modulo-2 polynomial division
  919. remainder <<= CHAR_BIT;
  920. remainder |= *new_dividend_bytes++;
  921. remainder ^= table.elems[ index ];
  922. }
  923. return remainder;
  924. }
  925. /** \brief Compute the updated remainder after reading some bytes
  926. The implementation reads from a table to speed-up applying
  927. unaugmented-CRC updates byte-wise.
  928. \param remainder The pre-update remainder
  929. \param new_dividend_bytes The address where the new bytes start
  930. \param new_dividend_byte_count The number of new bytes to read
  931. \return The updated remainder
  932. */
  933. static value_type crc_update( value_type remainder, unsigned char
  934. const *new_dividend_bytes, std::size_t new_dividend_byte_count)
  935. {
  936. static array_type const & table = base_type::get_table();
  937. while ( new_dividend_byte_count-- )
  938. {
  939. // Locates the merged partial product based on comparing the
  940. // leading and incoming bytes
  941. unsigned char const index = ( (remainder >> ( Order - CHAR_BIT
  942. )) & UCHAR_MAX ) ^ *new_dividend_bytes++;
  943. // Complete the multi-bit altered modulo-2 polynomial division
  944. remainder <<= CHAR_BIT;
  945. remainder ^= table.elems[ index ];
  946. }
  947. return remainder;
  948. }
  949. };
  950. /** \brief A mix-in class that handles reflected byte-fed, table-driven CRC
  951. algorithms
  952. This class template adds member functions #augmented_crc_update and
  953. #crc_update to update remainders from new input bytes. The bytes are
  954. reflected before processing.
  955. \pre \c CHAR_BIT \<= \a Order \<= \c std\::numeric_limits\<uintmax_t\>
  956. \::digits
  957. \tparam Order The order of the modulo-2 polynomial remainder and one
  958. less than the divisor's order.
  959. \tparam TruncatedPolynomial The lowest coefficients of the divisor
  960. polynomial. The highest-order coefficient is omitted and always
  961. assumed to be 1.
  962. */
  963. template < int Order, boost::uintmax_t TruncatedPolynomial >
  964. class reflected_byte_table_driven_crcs
  965. : public crc_table_t<Order, CHAR_BIT, TruncatedPolynomial, true>
  966. {
  967. typedef crc_table_t<Order, CHAR_BIT, TruncatedPolynomial, true>
  968. base_type;
  969. public:
  970. typedef typename base_type::value_type value_type;
  971. typedef typename base_type::array_type array_type;
  972. /** \brief Compute the updated remainder after reading some bytes
  973. The implementation reads from a table to speed-up applying
  974. reflecting augmented-CRC updates byte-wise.
  975. \param remainder The pre-update remainder; since the bytes are
  976. being reflected, this remainder also has to be reflected
  977. \param new_dividend_bytes The address where the new bytes start
  978. \param new_dividend_byte_count The number of new bytes to read
  979. \return The updated, reflected remainder
  980. */
  981. static value_type augmented_crc_update( value_type remainder, unsigned
  982. char const *new_dividend_bytes, std::size_t new_dividend_byte_count)
  983. {
  984. static array_type const & table = base_type::get_table();
  985. while ( new_dividend_byte_count-- )
  986. {
  987. // Locates the merged partial product based on the leading byte
  988. // (which is at the low-order end for reflected remainders)
  989. unsigned char const index = remainder & UCHAR_MAX;
  990. // Complete the multi-bit reflected modulo-2 polynomial division
  991. remainder >>= CHAR_BIT;
  992. remainder |= static_cast<value_type>( *new_dividend_bytes++ )
  993. << ( Order - CHAR_BIT );
  994. remainder ^= table.elems[ index ];
  995. }
  996. return remainder;
  997. }
  998. /** \brief Compute the updated remainder after reading some bytes
  999. The implementation reads from a table to speed-up applying
  1000. reflected unaugmented-CRC updates byte-wise.
  1001. \param remainder The pre-update remainder; since the bytes are
  1002. being reflected, this remainder also has to be reflected
  1003. \param new_dividend_bytes The address where the new bytes start
  1004. \param new_dividend_byte_count The number of new bytes to read
  1005. \return The updated, reflected remainder
  1006. */
  1007. static value_type crc_update( value_type remainder, unsigned char
  1008. const *new_dividend_bytes, std::size_t new_dividend_byte_count)
  1009. {
  1010. static array_type const & table = base_type::get_table();
  1011. while ( new_dividend_byte_count-- )
  1012. {
  1013. // Locates the merged partial product based on comparing the
  1014. // leading and incoming bytes
  1015. unsigned char const index = ( remainder & UCHAR_MAX ) ^
  1016. *new_dividend_bytes++;
  1017. // Complete the multi-bit reflected altered modulo-2 polynomial
  1018. // division
  1019. remainder >>= CHAR_BIT;
  1020. remainder ^= table.elems[ index ];
  1021. }
  1022. return remainder;
  1023. }
  1024. };
  1025. /** \brief Mix-in class for byte-fed, table-driven CRC algorithms with
  1026. parameter values at least a byte in width
  1027. This class template adds member functions #augmented_crc_update and
  1028. #crc_update to update remainders from new input bytes. The bytes may be
  1029. reflected before processing, controlled by a compile-time parameter.
  1030. \pre \c CHAR_BIT \<= \a Order \<= \c std\::numeric_limits\<uintmax_t\>
  1031. \::digits
  1032. \tparam Order The order of the modulo-2 polynomial remainder and one
  1033. less than the divisor's order.
  1034. \tparam TruncatedPolynomial The lowest coefficients of the divisor
  1035. polynomial. The highest-order coefficient is omitted and always
  1036. assumed to be 1.
  1037. \tparam Reflect If \c false, read from the highest-order bit from a new
  1038. input byte and go down, as normal. Otherwise, proceed from the
  1039. lowest-order bit and go up.
  1040. */
  1041. template < int Order, boost::uintmax_t TruncatedPolynomial, bool Reflect >
  1042. class byte_table_driven_crcs
  1043. : public boost::conditional< Reflect,
  1044. reflected_byte_table_driven_crcs<Order, TruncatedPolynomial>,
  1045. direct_byte_table_driven_crcs<Order, TruncatedPolynomial> >::type
  1046. { };
  1047. /** \brief A mix-in class that handles direct (i.e. non-reflected) byte-fed
  1048. CRC algorithms for sub-byte parameters
  1049. This class template adds member functions #augmented_crc_update and
  1050. #crc_update to update remainders from new input bytes. The bytes aren't
  1051. reflected before processing.
  1052. \pre 0 \< \a Order \< \c CHAR_BIT
  1053. \tparam Order The order of the modulo-2 polynomial remainder and one
  1054. less than the divisor's order.
  1055. \tparam TruncatedPolynomial The lowest coefficients of the divisor
  1056. polynomial. The highest-order coefficient is omitted and always
  1057. assumed to be 1.
  1058. */
  1059. template < int Order, boost::uintmax_t TruncatedPolynomial >
  1060. class direct_sub_byte_crcs
  1061. : public crc_table_t<Order, Order, TruncatedPolynomial, false>
  1062. {
  1063. typedef crc_table_t<Order, Order, TruncatedPolynomial, false>
  1064. base_type;
  1065. public:
  1066. typedef typename base_type::width_c width_c;
  1067. typedef typename base_type::value_type value_type;
  1068. typedef typename base_type::poly_c poly_c;
  1069. typedef typename base_type::array_type array_type;
  1070. /** \brief Compute the updated remainder after reading some bytes
  1071. The implementation reads from a table to speed-up applying
  1072. augmented-CRC updates byte-wise.
  1073. \param remainder The pre-update remainder
  1074. \param new_dividend_bytes The address where the new bytes start
  1075. \param new_dividend_byte_count The number of new bytes to read
  1076. \return The updated remainder
  1077. \todo Use this function somewhere so I can test it.
  1078. */
  1079. static value_type augmented_crc_update( value_type remainder, unsigned
  1080. char const *new_dividend_bytes, std::size_t new_dividend_byte_count)
  1081. {
  1082. //static array_type const & table = base_type::get_table();
  1083. while ( new_dividend_byte_count-- )
  1084. {
  1085. // Without a table, process each byte explicitly
  1086. augmented_crc_modulo_word_update( width_c::value, remainder,
  1087. *new_dividend_bytes++, poly_c::value, CHAR_BIT, false );
  1088. }
  1089. return remainder;
  1090. }
  1091. /** \brief Compute the updated remainder after reading some bytes
  1092. The implementation reads from a table to speed-up applying
  1093. unaugmented-CRC updates byte-wise.
  1094. \param remainder The pre-update remainder
  1095. \param new_dividend_bytes The address where the new bytes start
  1096. \param new_dividend_byte_count The number of new bytes to read
  1097. \return The updated remainder
  1098. */
  1099. static value_type crc_update( value_type remainder, unsigned char
  1100. const *new_dividend_bytes, std::size_t new_dividend_byte_count)
  1101. {
  1102. //static array_type const & table = base_type::get_table();
  1103. while ( new_dividend_byte_count-- )
  1104. {
  1105. // Without a table, process each byte explicitly
  1106. crc_modulo_word_update( width_c::value, remainder,
  1107. *new_dividend_bytes++, poly_c::value, CHAR_BIT, false );
  1108. }
  1109. return remainder;
  1110. }
  1111. };
  1112. /** \brief A mix-in class that handles reflected byte-fed, CRC algorithms
  1113. for sub-byte parameters
  1114. This class template adds member functions #augmented_crc_update and
  1115. #crc_update to update remainders from new input bytes. The bytes are
  1116. reflected before processing.
  1117. \pre 0 \< \a Order \< \c CHAR_BIT
  1118. \tparam Order The order of the modulo-2 polynomial remainder and one
  1119. less than the divisor's order.
  1120. \tparam TruncatedPolynomial The lowest coefficients of the divisor
  1121. polynomial. The highest-order coefficient is omitted and always
  1122. assumed to be 1.
  1123. */
  1124. template < int Order, boost::uintmax_t TruncatedPolynomial >
  1125. class reflected_sub_byte_crcs
  1126. : public crc_table_t<Order, Order, TruncatedPolynomial, true>
  1127. {
  1128. typedef crc_table_t<Order, Order, TruncatedPolynomial, true>
  1129. base_type;
  1130. public:
  1131. typedef typename base_type::width_c width_c;
  1132. typedef typename base_type::value_type value_type;
  1133. typedef typename base_type::poly_c poly_c;
  1134. typedef typename base_type::array_type array_type;
  1135. /** \brief Compute the updated remainder after reading some bytes
  1136. The implementation reads from a table to speed-up applying
  1137. reflecting augmented-CRC updates byte-wise.
  1138. \param remainder The pre-update remainder; since the bytes are
  1139. being reflected, this remainder also has to be reflected
  1140. \param new_dividend_bytes The address where the new bytes start
  1141. \param new_dividend_byte_count The number of new bytes to read
  1142. \return The updated, reflected remainder
  1143. \todo Use this function somewhere so I can test it.
  1144. */
  1145. static value_type augmented_crc_update( value_type remainder, unsigned
  1146. char const *new_dividend_bytes, std::size_t new_dividend_byte_count)
  1147. {
  1148. //static array_type const & table = base_type::get_table();
  1149. remainder = reflect_sub_byte( remainder, width_c::value );
  1150. while ( new_dividend_byte_count-- )
  1151. {
  1152. // Without a table, process each byte explicitly
  1153. augmented_crc_modulo_word_update( width_c::value, remainder,
  1154. *new_dividend_bytes++, poly_c::value, CHAR_BIT, true );
  1155. }
  1156. remainder = reflect_sub_byte( remainder, width_c::value );
  1157. return remainder;
  1158. }
  1159. /** \brief Compute the updated remainder after reading some bytes
  1160. The implementation reads from a table to speed-up applying
  1161. reflected unaugmented-CRC updates byte-wise.
  1162. \param remainder The pre-update remainder; since the bytes are
  1163. being reflected, this remainder also has to be reflected
  1164. \param new_dividend_bytes The address where the new bytes start
  1165. \param new_dividend_byte_count The number of new bytes to read
  1166. \return The updated, reflected remainder
  1167. */
  1168. static value_type crc_update( value_type remainder, unsigned char
  1169. const *new_dividend_bytes, std::size_t new_dividend_byte_count)
  1170. {
  1171. //static array_type const & table = base_type::get_table();
  1172. remainder = reflect_sub_byte( remainder, width_c::value );
  1173. while ( new_dividend_byte_count-- )
  1174. {
  1175. // Without a table, process each byte explicitly
  1176. crc_modulo_word_update( width_c::value, remainder,
  1177. *new_dividend_bytes++, poly_c::value, CHAR_BIT, true );
  1178. }
  1179. remainder = reflect_sub_byte( remainder, width_c::value );
  1180. return remainder;
  1181. }
  1182. };
  1183. /** \brief Mix-in class for byte-fed, table-driven CRC algorithms with
  1184. sub-byte parameters
  1185. This class template adds member functions #augmented_crc_update and
  1186. #crc_update to update remainders from new input bytes. The bytes may be
  1187. reflected before processing, controlled by a compile-time parameter.
  1188. \pre 0 \< \a Order \< \c CHAR_BIT
  1189. \tparam Order The order of the modulo-2 polynomial remainder and one
  1190. less than the divisor's order.
  1191. \tparam TruncatedPolynomial The lowest coefficients of the divisor
  1192. polynomial. The highest-order coefficient is omitted and always
  1193. assumed to be 1.
  1194. \tparam Reflect If \c false, read from the highest-order bit from a new
  1195. input byte and go down, as normal. Otherwise, proceed from the
  1196. lowest-order bit and go up.
  1197. */
  1198. template < int Order, boost::uintmax_t TruncatedPolynomial, bool Reflect >
  1199. class sub_byte_crcs
  1200. : public boost::conditional< Reflect,
  1201. reflected_sub_byte_crcs<Order, TruncatedPolynomial>,
  1202. direct_sub_byte_crcs<Order, TruncatedPolynomial> >::type
  1203. { };
  1204. /** This class template adds member functions #augmented_crc_update and
  1205. #crc_update to update remainders from new input bytes. The bytes may be
  1206. reflected before processing, controlled by a compile-time parameter.
  1207. \pre 0 \< \a Order \<= \c std\::numeric_limits\<uintmax_t\>\::digits
  1208. \tparam Order The order of the modulo-2 polynomial remainder and one
  1209. less than the divisor's order.
  1210. \tparam TruncatedPolynomial The lowest coefficients of the divisor
  1211. polynomial. The highest-order coefficient is omitted and always
  1212. assumed to be 1.
  1213. \tparam Reflect If \c false, read from the highest-order bit from a new
  1214. input byte and go down, as normal. Otherwise, proceed from the
  1215. lowest-order bit and go up.
  1216. \tparam Id An extra differentiator if multiple copies of this class
  1217. template are mixed-in as base classes. Defaults to 0 if omitted.
  1218. */
  1219. template < int Order, boost::uintmax_t TruncatedPolynomial, bool Reflect,
  1220. int Id >
  1221. class crc_driver
  1222. : public boost::conditional< (Order < CHAR_BIT), sub_byte_crcs<Order,
  1223. TruncatedPolynomial, Reflect>, byte_table_driven_crcs<Order,
  1224. TruncatedPolynomial, Reflect> >::type
  1225. {
  1226. public:
  1227. /** \brief The type to check for ID
  1228. This is a Boost integral constant indicating what ID number this
  1229. instantiation used.
  1230. */
  1231. typedef boost::integral_constant<int, Id> id_type;
  1232. };
  1233. } // namespace detail
  1234. //! \endcond
  1235. // Simple CRC class function definitions -----------------------------------//
  1236. /** Constructs a \c crc_basic object with at least the required parameters to a
  1237. particular CRC formula to be processed upon receiving input.
  1238. \param[in] truncated_polynomial The lowest coefficients of the divisor
  1239. polynomial. The highest-order coefficient is omitted and always assumed
  1240. to be 1. (\e Poly from the RMCA)
  1241. \param[in] initial_remainder The (unaugmented) initial state of the
  1242. polynomial remainder. Defaults to \c 0 if omitted. (\e Init from the
  1243. RMCA)
  1244. \param[in] final_xor_value The (XOR) bit-mask to be applied to the output
  1245. remainder, after possible reflection but before returning. Defaults to
  1246. \c 0 (i.e. no bit changes) if omitted. (\e XorOut from the RMCA)
  1247. \param[in] reflect_input If \c true, input bytes are read lowest-order bit
  1248. first, otherwise highest-order bit first. Defaults to \c false if
  1249. omitted. (\e RefIn from the RMCA)
  1250. \param[in] reflect_remainder If \c true, the output remainder is reflected
  1251. before the XOR-mask. Defaults to \c false if omitted. (\e RefOut from
  1252. the RMCA)
  1253. \post <code><var>truncated_polynomial</var> ==
  1254. this-&gt;get_truncated_polynominal()</code>
  1255. \post <code><var>initial_remainder</var> ==
  1256. this-&gt;get_initial_remainder()</code>
  1257. \post <code><var>final_xor_value</var> ==
  1258. this-&gt;get_final_xor_value()</code>
  1259. \post <code><var>reflect_input</var> ==
  1260. this-&gt;get_reflect_input()</code>
  1261. \post <code><var>reflect_remainder</var> ==
  1262. this-&gt;get_reflect_remainder()</code>
  1263. \post <code><var>initial_remainder</var> ==
  1264. this-&gt;get_interim_remainder()</code>
  1265. \post <code>(<var>reflect_remainder</var> ?
  1266. REFLECT(<var>initial_remainder</var>) : <var>initial_remainder</var>) ^
  1267. <var>final_xor_value</var> == this-&gt;checksum()</code>
  1268. */
  1269. template < std::size_t Bits >
  1270. inline
  1271. crc_basic<Bits>::crc_basic
  1272. (
  1273. value_type truncated_polynomial,
  1274. value_type initial_remainder, // = 0
  1275. value_type final_xor_value, // = 0
  1276. bool reflect_input, // = false
  1277. bool reflect_remainder // = false
  1278. )
  1279. : rem_( initial_remainder ), poly_( truncated_polynomial )
  1280. , init_( initial_remainder ), final_( final_xor_value )
  1281. , rft_in_( reflect_input ), rft_out_( reflect_remainder )
  1282. {
  1283. }
  1284. /** Returns a representation of the polynomial divisor. The value of the
  1285. 2<sup>i</sup> bit is the value of the coefficient of the polynomial's
  1286. x<sup>i</sup> term. The omitted bit for x<sup>(#bit_count)</sup> term is
  1287. always 1.
  1288. \return The bit-packed list of coefficients. If the bit-length of
  1289. #value_type exceeds #bit_count, the values of higher-placed bits should be
  1290. ignored (even any for x<sup>(#bit_count)</sup>) since they're unregulated.
  1291. */
  1292. template < std::size_t Bits >
  1293. inline
  1294. typename crc_basic<Bits>::value_type
  1295. crc_basic<Bits>::get_truncated_polynominal
  1296. (
  1297. ) const
  1298. {
  1299. return poly_;
  1300. }
  1301. /** Returns a representation of the polynomial remainder before any input has
  1302. been submitted. The value of the 2<sup>i</sup> bit is the value of the
  1303. coefficient of the polynomial's x<sup>i</sup> term.
  1304. \return The bit-packed list of coefficients. If the bit-length of
  1305. #value_type exceeds #bit_count, the values of higher-placed bits should be
  1306. ignored since they're unregulated.
  1307. */
  1308. template < std::size_t Bits >
  1309. inline
  1310. typename crc_basic<Bits>::value_type
  1311. crc_basic<Bits>::get_initial_remainder
  1312. (
  1313. ) const
  1314. {
  1315. return init_;
  1316. }
  1317. /** Returns the mask to be used during creation of a checksum. The mask is used
  1318. for an exclusive-or (XOR) operation applied bit-wise to the interim
  1319. remainder representation (after any reflection, if #get_reflect_remainder()
  1320. returns \c true).
  1321. \return The bit-mask. If the bit-length of #value_type exceeds #bit_count,
  1322. the values of higher-placed bits should be ignored since they're
  1323. unregulated.
  1324. */
  1325. template < std::size_t Bits >
  1326. inline
  1327. typename crc_basic<Bits>::value_type
  1328. crc_basic<Bits>::get_final_xor_value
  1329. (
  1330. ) const
  1331. {
  1332. return final_;
  1333. }
  1334. /** Returns a whether or not a submitted byte will be \"reflected\" before it is
  1335. used to update the interim remainder. Only the byte-wise operations
  1336. #process_byte, #process_block, and #process_bytes are affected.
  1337. \retval true Input bytes will be read starting from the lowest-order bit.
  1338. \retval false Input bytes will be read starting from the highest-order bit.
  1339. */
  1340. template < std::size_t Bits >
  1341. inline
  1342. bool
  1343. crc_basic<Bits>::get_reflect_input
  1344. (
  1345. ) const
  1346. {
  1347. return rft_in_;
  1348. }
  1349. /** Indicates if the interim remainder will be \"reflected\" before it is passed
  1350. to the XOR-mask stage when returning a checksum.
  1351. \retval true The interim remainder is reflected before further work.
  1352. \retval false The interim remainder is applied to the XOR-mask as-is.
  1353. */
  1354. template < std::size_t Bits >
  1355. inline
  1356. bool
  1357. crc_basic<Bits>::get_reflect_remainder
  1358. (
  1359. ) const
  1360. {
  1361. return rft_out_;
  1362. }
  1363. /** Returns a representation of the polynomial remainder after all the input
  1364. submissions since construction or the last #reset call. The value of the
  1365. 2<sup>i</sup> bit is the value of the coefficient of the polynomial's
  1366. x<sup>i</sup> term. If CRC processing gets interrupted here, retain the
  1367. value returned, and use it to start up the next CRC computer where you left
  1368. off (with #reset(value_type) or construction). The next computer has to
  1369. have its other parameters compatible with this computer.
  1370. \return The bit-packed list of coefficients. If the bit-length of
  1371. #value_type exceeds #bit_count, the values of higher-placed bits should be
  1372. ignored since they're unregulated. No output processing (reflection or
  1373. XOR mask) has been applied to the value.
  1374. */
  1375. template < std::size_t Bits >
  1376. inline
  1377. typename crc_basic<Bits>::value_type
  1378. crc_basic<Bits>::get_interim_remainder
  1379. (
  1380. ) const
  1381. {
  1382. return rem_ & detail::low_bits_mask_c<bit_count>::value;
  1383. }
  1384. /** Changes the interim polynomial remainder to \a new_rem, purging any
  1385. influence previously submitted input has had. The value of the
  1386. 2<sup>i</sup> bit is the value of the coefficient of the polynomial's
  1387. x<sup>i</sup> term.
  1388. \param[in] new_rem The (unaugmented) state of the polynomial remainder
  1389. starting from this point, with no output processing applied.
  1390. \post <code><var>new_rem</var> == this-&gt;get_interim_remainder()</code>
  1391. \post <code>((this-&gt;get_reflect_remainder() ?
  1392. REFLECT(<var>new_rem</var>) : <var>new_rem</var>) ^
  1393. this-&gt;get_final_xor_value()) == this-&gt;checksum()</code>
  1394. */
  1395. template < std::size_t Bits >
  1396. inline
  1397. void
  1398. crc_basic<Bits>::reset
  1399. (
  1400. value_type new_rem
  1401. )
  1402. {
  1403. rem_ = new_rem;
  1404. }
  1405. /** Changes the interim polynomial remainder to the initial remainder given
  1406. during construction, purging any influence previously submitted input has
  1407. had. The value of the 2<sup>i</sup> bit is the value of the coefficient of
  1408. the polynomial's x<sup>i</sup> term.
  1409. \post <code>this-&gt;get_initial_remainder() ==
  1410. this-&gt;get_interim_remainder()</code>
  1411. \post <code>((this-&gt;get_reflect_remainder() ?
  1412. REFLECT(this-&gt;get_initial_remainder()) :
  1413. this-&gt;get_initial_remainder()) ^ this-&gt;get_final_xor_value())
  1414. == this-&gt;checksum()</code>
  1415. */
  1416. template < std::size_t Bits >
  1417. inline
  1418. void
  1419. crc_basic<Bits>::reset
  1420. (
  1421. )
  1422. {
  1423. this->reset( this->get_initial_remainder() );
  1424. }
  1425. /** Updates the interim remainder with a single altered-CRC-division step.
  1426. \param[in] bit The new input bit.
  1427. \post The interim remainder is updated though a modulo-2 polynomial
  1428. division, where the division steps are altered for unaugmented CRCs.
  1429. */
  1430. template < std::size_t Bits >
  1431. inline
  1432. void
  1433. crc_basic<Bits>::process_bit
  1434. (
  1435. bool bit
  1436. )
  1437. {
  1438. detail::crc_modulo_update( bit_count, rem_, bit, poly_ );
  1439. }
  1440. /** Updates the interim remainder with several altered-CRC-division steps. Each
  1441. bit is processed separately, starting from the one at the
  1442. 2<sup><var>bit_length</var> - 1</sup> place, then proceeding down to the
  1443. lowest-placed bit. Any order imposed by
  1444. <code>this-&gt;get_reflect_input()</code> is ignored.
  1445. \pre 0 \< \a bit_length \<= \c CHAR_BIT
  1446. \param[in] bits The byte containing the new input bits.
  1447. \param[in] bit_length The number of bits in the byte to be read.
  1448. \post The interim remainder is updated though \a bit_length modulo-2
  1449. polynomial divisions, where the division steps are altered for unaugmented
  1450. CRCs.
  1451. */
  1452. template < std::size_t Bits >
  1453. void
  1454. crc_basic<Bits>::process_bits
  1455. (
  1456. unsigned char bits,
  1457. std::size_t bit_length
  1458. )
  1459. {
  1460. // ignore the bits above the ones we want
  1461. bits <<= CHAR_BIT - bit_length;
  1462. // compute the CRC for each bit, starting with the upper ones
  1463. unsigned char const high_bit_mask = 1u << ( CHAR_BIT - 1u );
  1464. for ( std::size_t i = bit_length ; i > 0u ; --i, bits <<= 1u )
  1465. {
  1466. process_bit( (bits & high_bit_mask) != 0 );
  1467. }
  1468. }
  1469. /** Updates the interim remainder with a byte's worth of altered-CRC-division
  1470. steps. The bits within the byte are processed from the highest place down
  1471. if <code>this-&gt;get_reflect_input()</code> is \c false, and lowest place
  1472. up otherwise.
  1473. \param[in] byte The new input byte.
  1474. \post The interim remainder is updated though \c CHAR_BIT modulo-2
  1475. polynomial divisions, where the division steps are altered for unaugmented
  1476. CRCs.
  1477. */
  1478. template < std::size_t Bits >
  1479. inline
  1480. void
  1481. crc_basic<Bits>::process_byte
  1482. (
  1483. unsigned char byte
  1484. )
  1485. {
  1486. process_bits( (rft_in_ ? detail::reflect_byte( byte ) : byte), CHAR_BIT );
  1487. }
  1488. /** Updates the interim remainder with several bytes' worth of
  1489. altered-CRC-division steps. The bits within each byte are processed from
  1490. the highest place down if <code>this-&gt;get_reflect_input()</code> is
  1491. \c false, and lowest place up otherwise. The bytes themselves are processed
  1492. starting from the one pointed by \a bytes_begin until \a bytes_end is
  1493. reached through forward iteration, treating the two pointers as if they
  1494. point to <code>unsigned char</code> objects.
  1495. \pre \a bytes_end has to equal \a bytes_begin if the latter is \c NULL or
  1496. otherwise doesn't point to a valid buffer.
  1497. \pre \a bytes_end, if not equal to \a bytes_begin, has to point within or
  1498. one-byte-past the same buffer \a bytes_begin points into.
  1499. \pre \a bytes_end has to be reachable from \a bytes_begin through a finite
  1500. number of forward byte-pointer increments.
  1501. \param[in] bytes_begin The address where the memory block begins.
  1502. \param[in] bytes_end Points to one-byte past the address of the memory
  1503. block's last byte, or \a bytes_begin if no bytes are to be read.
  1504. \post The interim remainder is updated though <code>CHAR_BIT * (((unsigned
  1505. char const *) bytes_end) - ((unsigned char const *) bytes_begin))</code>
  1506. modulo-2 polynomial divisions, where the division steps are altered for
  1507. unaugmented CRCs.
  1508. */
  1509. template < std::size_t Bits >
  1510. void
  1511. crc_basic<Bits>::process_block
  1512. (
  1513. void const * bytes_begin,
  1514. void const * bytes_end
  1515. )
  1516. {
  1517. for ( unsigned char const * p
  1518. = static_cast<unsigned char const *>(bytes_begin) ; p < bytes_end ; ++p )
  1519. {
  1520. process_byte( *p );
  1521. }
  1522. }
  1523. /** Updates the interim remainder with several bytes' worth of
  1524. altered-CRC-division steps. The bits within each byte are processed from
  1525. the highest place down if <code>this-&gt;get_reflect_input()</code> is
  1526. \c false, and lowest place up otherwise. The bytes themselves are processed
  1527. starting from the one pointed by \a buffer, forward-iterated (as if the
  1528. pointed-to objects were of <code>unsigned char</code>) until \a byte_count
  1529. bytes are read.
  1530. \pre \a byte_count has to equal 0 if \a buffer is \c NULL or otherwise
  1531. doesn't point to valid memory.
  1532. \pre If \a buffer points within valid memory, then that block has to have
  1533. at least \a byte_count more valid bytes allocated from that point.
  1534. \param[in] buffer The address where the memory block begins.
  1535. \param[in] byte_count The number of bytes in the memory block.
  1536. \post The interim remainder is updated though <code>CHAR_BIT *
  1537. <var>byte_count</var></code> modulo-2 polynomial divisions, where the
  1538. division steps are altered for unaugmented CRCs.
  1539. */
  1540. template < std::size_t Bits >
  1541. inline
  1542. void
  1543. crc_basic<Bits>::process_bytes
  1544. (
  1545. void const * buffer,
  1546. std::size_t byte_count
  1547. )
  1548. {
  1549. unsigned char const * const b = static_cast<unsigned char const *>(
  1550. buffer );
  1551. process_block( b, b + byte_count );
  1552. }
  1553. /** Computes the checksum of all the submitted bits since construction or the
  1554. last call to #reset. The checksum will be the raw checksum, i.e. the
  1555. (interim) remainder after all the modulo-2 polynomial division, plus any
  1556. output processing.
  1557. \return <code>(this-&gt;get_reflect_remainder() ?
  1558. REFLECT(this-&gt;get_interim_remainder()) :
  1559. this-&gt;get_interim_remainder()) ^ this-&gt;get_final_xor_value()</code>
  1560. \note Since checksums are meant to be compared, any higher-placed bits
  1561. (when the bit-length of #value_type exceeds #bit_count) will be set to 0.
  1562. */
  1563. template < std::size_t Bits >
  1564. inline
  1565. typename crc_basic<Bits>::value_type
  1566. crc_basic<Bits>::checksum
  1567. (
  1568. ) const
  1569. {
  1570. return ( (rft_out_ ? detail::reflect_unsigned( rem_, bit_count ) :
  1571. rem_) ^ final_ ) & detail::low_bits_mask_c<bit_count>::value;
  1572. }
  1573. // Optimized CRC class function definitions --------------------------------//
  1574. // Macro to compact code
  1575. #define BOOST_CRC_OPTIMAL_NAME crc_optimal<Bits, TruncPoly, InitRem, \
  1576. FinalXor, ReflectIn, ReflectRem>
  1577. /** Constructs a \c crc_optimal object with a particular CRC formula to be
  1578. processed upon receiving input. The initial remainder may be overridden.
  1579. \param[in] init_rem The (unaugmented) initial state of the polynomial
  1580. remainder. Defaults to #initial_remainder if omitted.
  1581. \post <code>#truncated_polynominal ==
  1582. this-&gt;get_truncated_polynominal()</code>
  1583. \post <code>#initial_remainder == this-&gt;get_initial_remainder()</code>
  1584. \post <code>#final_xor_value == this-&gt;get_final_xor_value()</code>
  1585. \post <code>#reflect_input == this-&gt;get_reflect_input()</code>
  1586. \post <code>#reflect_remainder == this-&gt;get_reflect_remainder()</code>
  1587. \post <code><var>init_rem</var> == this-&gt;get_interim_remainder()</code>
  1588. \post <code>(#reflect_remainder ? REFLECT(<var>init_rem</var>) :
  1589. <var>init_rem</var>) ^ #final_xor_value == this-&gt;checksum()</code>
  1590. */
  1591. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1592. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1593. bool ReflectIn, bool ReflectRem >
  1594. inline
  1595. BOOST_CRC_OPTIMAL_NAME::crc_optimal
  1596. (
  1597. value_type init_rem // = initial_remainder
  1598. )
  1599. : rem_( reflect_i_type::reflect_q(init_rem) )
  1600. {
  1601. }
  1602. //! \copydetails boost::crc_basic::get_truncated_polynominal
  1603. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1604. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1605. bool ReflectIn, bool ReflectRem >
  1606. inline
  1607. typename BOOST_CRC_OPTIMAL_NAME::value_type
  1608. BOOST_CRC_OPTIMAL_NAME::get_truncated_polynominal
  1609. (
  1610. ) const
  1611. {
  1612. return truncated_polynominal;
  1613. }
  1614. //! \copydetails boost::crc_basic::get_initial_remainder
  1615. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1616. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1617. bool ReflectIn, bool ReflectRem >
  1618. inline
  1619. typename BOOST_CRC_OPTIMAL_NAME::value_type
  1620. BOOST_CRC_OPTIMAL_NAME::get_initial_remainder
  1621. (
  1622. ) const
  1623. {
  1624. return initial_remainder;
  1625. }
  1626. //! \copydetails boost::crc_basic::get_final_xor_value
  1627. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1628. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1629. bool ReflectIn, bool ReflectRem >
  1630. inline
  1631. typename BOOST_CRC_OPTIMAL_NAME::value_type
  1632. BOOST_CRC_OPTIMAL_NAME::get_final_xor_value
  1633. (
  1634. ) const
  1635. {
  1636. return final_xor_value;
  1637. }
  1638. //! \copydetails boost::crc_basic::get_reflect_input
  1639. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1640. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1641. bool ReflectIn, bool ReflectRem >
  1642. inline
  1643. bool
  1644. BOOST_CRC_OPTIMAL_NAME::get_reflect_input
  1645. (
  1646. ) const
  1647. {
  1648. return reflect_input;
  1649. }
  1650. //! \copydetails boost::crc_basic::get_reflect_remainder
  1651. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1652. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1653. bool ReflectIn, bool ReflectRem >
  1654. inline
  1655. bool
  1656. BOOST_CRC_OPTIMAL_NAME::get_reflect_remainder
  1657. (
  1658. ) const
  1659. {
  1660. return reflect_remainder;
  1661. }
  1662. //! \copydetails boost::crc_basic::get_interim_remainder
  1663. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1664. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1665. bool ReflectIn, bool ReflectRem >
  1666. inline
  1667. typename BOOST_CRC_OPTIMAL_NAME::value_type
  1668. BOOST_CRC_OPTIMAL_NAME::get_interim_remainder
  1669. (
  1670. ) const
  1671. {
  1672. // Interim remainder should be _un_-reflected, so we have to undo it.
  1673. return reflect_i_type::reflect_q( rem_ ) &
  1674. detail::low_bits_mask_c<bit_count>::value;
  1675. }
  1676. /** Changes the interim polynomial remainder to \a new_rem, purging any
  1677. influence previously submitted input has had. The value of the
  1678. 2<sup>i</sup> bit is the value of the coefficient of the polynomial's
  1679. x<sup>i</sup> term.
  1680. \param[in] new_rem The (unaugmented) state of the polynomial remainder
  1681. starting from this point, with no output processing applied. Defaults to
  1682. <code>this-&gt;get_initial_remainder()</code> if omitted.
  1683. \post <code><var>new_rem</var> == this-&gt;get_interim_remainder()</code>
  1684. \post <code>((this-&gt;get_reflect_remainder() ?
  1685. REFLECT(<var>new_rem</var>) : <var>new_rem</var>) ^
  1686. this-&gt;get_final_xor_value()) == this-&gt;checksum()</code>
  1687. */
  1688. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1689. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1690. bool ReflectIn, bool ReflectRem >
  1691. inline
  1692. void
  1693. BOOST_CRC_OPTIMAL_NAME::reset
  1694. (
  1695. value_type new_rem // = initial_remainder
  1696. )
  1697. {
  1698. rem_ = reflect_i_type::reflect_q( new_rem );
  1699. }
  1700. /** \copydetails boost::crc_basic::process_byte
  1701. \note Any modulo-2 polynomial divisions may use a table of pre-computed
  1702. remainder changes (as XOR masks) to speed computation when reading data
  1703. byte-wise.
  1704. */
  1705. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1706. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1707. bool ReflectIn, bool ReflectRem >
  1708. inline
  1709. void
  1710. BOOST_CRC_OPTIMAL_NAME::process_byte
  1711. (
  1712. unsigned char byte
  1713. )
  1714. {
  1715. process_bytes( &byte, sizeof(byte) );
  1716. }
  1717. /** \copydetails boost::crc_basic::process_block
  1718. \note Any modulo-2 polynomial divisions may use a table of pre-computed
  1719. remainder changes (as XOR masks) to speed computation when reading data
  1720. byte-wise.
  1721. */
  1722. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1723. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1724. bool ReflectIn, bool ReflectRem >
  1725. inline
  1726. void
  1727. BOOST_CRC_OPTIMAL_NAME::process_block
  1728. (
  1729. void const * bytes_begin,
  1730. void const * bytes_end
  1731. )
  1732. {
  1733. process_bytes( bytes_begin, static_cast<unsigned char const *>(bytes_end) -
  1734. static_cast<unsigned char const *>(bytes_begin) );
  1735. }
  1736. /** \copydetails boost::crc_basic::process_bytes
  1737. \note Any modulo-2 polynomial divisions may use a table of pre-computed
  1738. remainder changes (as XOR masks) to speed computation when reading data
  1739. byte-wise.
  1740. */
  1741. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1742. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1743. bool ReflectIn, bool ReflectRem >
  1744. inline
  1745. void
  1746. BOOST_CRC_OPTIMAL_NAME::process_bytes
  1747. (
  1748. void const * buffer,
  1749. std::size_t byte_count
  1750. )
  1751. {
  1752. rem_ = crc_table_type::crc_update( rem_, static_cast<unsigned char const
  1753. *>(buffer), byte_count );
  1754. }
  1755. //! \copydetails boost::crc_basic::checksum
  1756. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1757. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1758. bool ReflectIn, bool ReflectRem >
  1759. inline
  1760. typename BOOST_CRC_OPTIMAL_NAME::value_type
  1761. BOOST_CRC_OPTIMAL_NAME::checksum
  1762. (
  1763. ) const
  1764. {
  1765. return ( reflect_o_type::reflect_q(rem_) ^ get_final_xor_value() )
  1766. & detail::low_bits_mask_c<bit_count>::value;
  1767. }
  1768. /** Updates the interim remainder with a byte's worth of altered-CRC-division
  1769. steps. The bits within the byte are processed from the highest place down
  1770. if <code>this-&gt;get_reflect_input()</code> is \c false, and lowest place
  1771. up otherwise. This function is meant to present a function-object interface
  1772. to code that wants to process a stream of bytes with
  1773. <code>std::for_each</code> or similar range-processing algorithms. Since
  1774. some of these algorithms takes their function object by value, make sure to
  1775. copy back the result to this object so the updates can be remembered.
  1776. \param[in] byte The new input byte.
  1777. \post The interim remainder is updated though \c CHAR_BIT modulo-2
  1778. polynomial divisions, where the division steps are altered for unaugmented
  1779. CRCs.
  1780. \note Any modulo-2 polynomial divisions may use a table of pre-computed
  1781. remainder changes (as XOR masks) to speed computation when reading data
  1782. byte-wise.
  1783. */
  1784. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1785. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1786. bool ReflectIn, bool ReflectRem >
  1787. inline
  1788. void
  1789. BOOST_CRC_OPTIMAL_NAME::operator ()
  1790. (
  1791. unsigned char byte
  1792. )
  1793. {
  1794. process_byte( byte );
  1795. }
  1796. /** Computes the checksum of all the submitted bits since construction or the
  1797. last call to #reset. The checksum will be the raw checksum, i.e. the
  1798. (interim) remainder after all the modulo-2 polynomial division, plus any
  1799. output processing. This function is meant to present a function-object
  1800. interface to code that wants to receive data like
  1801. <code>std::generate_n</code> or similar data-processing algorithms. Note
  1802. that if this object is used as a generator multiple times without an
  1803. intervening mutating operation, the same value will always be returned.
  1804. \return <code>(this-&gt;get_reflect_remainder() ?
  1805. REFLECT(this-&gt;get_interim_remainder()) :
  1806. this-&gt;get_interim_remainder()) ^ this-&gt;get_final_xor_value()</code>
  1807. \note Since checksums are meant to be compared, any higher-placed bits
  1808. (when the bit-length of #value_type exceeds #bit_count) will be set to 0.
  1809. */
  1810. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1811. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1812. bool ReflectIn, bool ReflectRem >
  1813. inline
  1814. typename BOOST_CRC_OPTIMAL_NAME::value_type
  1815. BOOST_CRC_OPTIMAL_NAME::operator ()
  1816. (
  1817. ) const
  1818. {
  1819. return checksum();
  1820. }
  1821. // CRC computation function definition -------------------------------------//
  1822. /** Computes the polynomial remainder of a CRC run, assuming that \a buffer and
  1823. \a byte_count describe a memory block representing the polynomial dividend.
  1824. The division steps are altered so the result directly gives a checksum,
  1825. without need to augment the memory block with scratch-space bytes. The
  1826. first byte is considered the highest order, going down for subsequent bytes.
  1827. \pre 0 \< \a Bits \<= \c std\::numeric_limits\<uintmax_t\>\::digits
  1828. \tparam Bits The order of the modulo-2 polynomial divisor. (\e Width from
  1829. the RMCA)
  1830. \tparam TruncPoly The lowest coefficients of the divisor polynomial. The
  1831. highest-order coefficient is omitted and always assumed to be 1.
  1832. (\e Poly from the RMCA)
  1833. \tparam InitRem The (unaugmented) initial state of the polynomial
  1834. remainder. (\e Init from the RMCA)
  1835. \tparam FinalXor The (XOR) bit-mask to be applied to the output remainder,
  1836. after possible reflection but before returning. (\e XorOut from the RMCA)
  1837. \tparam ReflectIn If \c True, input bytes are read lowest-order bit first,
  1838. otherwise highest-order bit first. (\e RefIn from the RMCA)
  1839. \tparam ReflectRem If \c True, the output remainder is reflected before the
  1840. XOR-mask. (\e RefOut from the RMCA)
  1841. \param[in] buffer The address where the memory block begins.
  1842. \param[in] byte_count The number of bytes in the memory block.
  1843. \return The checksum, which is the last (interim) remainder plus any output
  1844. processing.
  1845. \note Unaugmented-style CRC runs perform modulo-2 polynomial division in
  1846. an altered order. The trailing \a Bits number of zero-valued bits needed
  1847. to extracted an (unprocessed) checksum is virtually moved to near the
  1848. beginning of the message. This is OK since the XOR operation is
  1849. commutative and associative. It also means that you can get a checksum
  1850. anytime. Since data is being read byte-wise, a table of pre-computed
  1851. remainder changes (as XOR masks) can be used to speed computation.
  1852. */
  1853. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  1854. BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  1855. bool ReflectIn, bool ReflectRem >
  1856. inline
  1857. typename uint_t<Bits>::fast
  1858. crc
  1859. (
  1860. void const * buffer,
  1861. std::size_t byte_count
  1862. )
  1863. {
  1864. BOOST_CRC_OPTIMAL_NAME computer;
  1865. computer.process_bytes( buffer, byte_count );
  1866. return computer.checksum();
  1867. }
  1868. // Augmented-message CRC computation function definition -------------------//
  1869. /** Computes the polynomial remainder of a CRC run, assuming that \a buffer and
  1870. \a byte_count describe a memory block representing the polynomial dividend.
  1871. The first byte is considered the highest order, going down for subsequent
  1872. bytes. Within a byte, the highest-order bit is read first (corresponding to
  1873. \e RefIn = \c False in the RMCA). Check the other parts of this function's
  1874. documentation to see how a checksum can be gained and/or used.
  1875. \pre 0 \< \a Bits \<= \c std\::numeric_limit\<uintmax_t\>\::digits
  1876. \tparam Bits The order of the modulo-2 polynomial divisor. (\e Width from
  1877. the RMCA)
  1878. \tparam TruncPoly The lowest coefficients of the divisor polynomial. The
  1879. highest-order coefficient is omitted and always assumed to be 1.
  1880. (\e Poly from the RMCA)
  1881. \param[in] buffer The address where the memory block begins.
  1882. \param[in] byte_count The number of bytes in the memory block.
  1883. \param[in] initial_remainder The initial state of the polynomial
  1884. remainder, defaulting to zero if omitted. If you are reading a memory
  1885. block in multiple runs, put the return value of the previous run here.
  1886. (Note that initial-remainders given by RMCA parameter lists, as
  1887. \e Init, assume that the initial remainder is in its \b unaugmented state,
  1888. so you would need to convert the value to make it suitable for this
  1889. function. I currently don't provide a conversion routine.)
  1890. \return The interim remainder, if no augmentation is used. A special value
  1891. if augmentation is used (see the notes). No output processing is done on
  1892. the value. (In RMCA terms, \e RefOut is \c False and \e XorOut is \c 0.)
  1893. \note Augmented-style CRC runs use straight-up modulo-2 polynomial
  1894. division. Since data is being read byte-wise, a table of pre-computed
  1895. remainder changes (as XOR masks) can be used to speed computation.
  1896. \note Reading just a memory block will yield an interim remainder, and not
  1897. the final checksum. To get that checksum, allocate \a Bits / \c CHAR_BIT
  1898. bytes directly after the block and fill them with zero values, then extend
  1899. \a byte_count to include those extra bytes. A data block is corrupt if
  1900. the return value doesn't equal your separately given checksum.
  1901. \note Another way to perform a check is use the zero-byte extension method,
  1902. but replace the zero values with your separately-given checksum. The
  1903. checksum must be loaded in big-endian order. Here corruption, in either
  1904. the data block or the given checksum, is confirmed if the return value is
  1905. not zero.
  1906. \note The two checksum techniques assume the CRC-run is performed bit-wise,
  1907. while this function works byte-wise. That means that the techniques can
  1908. be used only if \c CHAR_BIT divides \a Bits evenly!
  1909. */
  1910. template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly >
  1911. typename uint_t<Bits>::fast
  1912. augmented_crc
  1913. (
  1914. void const * buffer,
  1915. std::size_t byte_count,
  1916. typename uint_t<Bits>::fast initial_remainder // = 0u
  1917. )
  1918. {
  1919. return detail::low_bits_mask_c<Bits>::value &
  1920. detail::byte_table_driven_crcs<Bits, TruncPoly, false>::
  1921. augmented_crc_update( initial_remainder, static_cast<unsigned char const
  1922. *>(buffer), byte_count );
  1923. }
  1924. } // namespace boost
  1925. // Undo header-private macros
  1926. #undef BOOST_CRC_OPTIMAL_NAME
  1927. #undef BOOST_CRC_PARM_TYPE
  1928. #endif // BOOST_CRC_HPP