fec 0.1.1 → 0.2.0

raw patch · 13 files changed

+1491/−590 lines, 13 filesdep +QuickCheckdep +criteriondep +data-serializerdep ~basedep ~bytestringsetup-changednew-component:exe:benchmark-zfecnew-uploaderPVP ok

version bump matches the API change (PVP)

Dependencies added: QuickCheck, criterion, data-serializer, deepseq, extra, fec, hspec, quickcheck-instances, random

Dependency ranges changed: base, bytestring

API changes (from Hackage documentation)

Files

• COPYING.GPL +110/−4
• COPYING.TGPPL.html +0/−80
• COPYING.TGPPL.rst +291/−0
• ChangeLog.md +10/−0
• README.rst +327/−0
• README.txt +0/−252
• Setup.lhs +0/−3
• benchmark-zfec/Main.hs +93/−0
• fec.cabal +77/−30
• haskell/Codec/FEC.hs +350/−192
• haskell/test/FECTest.hs +153/−0
• zfec/fec.c +63/−26
• zfec/fec.h +17/−3

@@ -1,7 +1,113 @@-This licence also comes with the added permission that you may link this-program with the OpenSSL library and distribute executables, as long as you-follow the requirements of this licence in regard to all of the software in-the executable aside from OpenSSL.+This work also comes with the added permission that you may combine it with a+work licensed under the OpenSSL license (any version) and distribute the+resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the OpenSSL license.++This work also comes with the added permission that you may combine it with a+work licensed under the Eclipse Public Licence (any version) and distribute+the resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Eclipse Public Licence.++This work also comes with the added permission that you may combine it with a+work licensed under the Q Public Licence (any version) and distribute the+resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Q Public Licence.++This work also comes with the added permission that you may combine it with a+work licensed under the Apache Licence (any version) and distribute the+resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Apache Licence.++This work also comes with the added permission that you may combine it with a+work licensed under the GNU Lesser General Public License (any version) and+distribute the resulting combined work, as long as you follow the+requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the GNU Lesser+General Public License.++This work also comes with the added permission that you may combine it with a+work licensed under the Zope Public License (any version) and distribute the+resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Zope Public License.++This work also comes with the added permission that you may combine it with a+work licensed under the Python Software Foundation License (any version) and+distribute the resulting combined work, as long as you follow the+requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the Python+Software Foundation License.++This work also comes with the added permission that you may combine it with a+work licensed under the Academic Free License (any version) and distribute+the resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Academic Free License.++This work also comes with the added permission that you may combine it with a+work licensed under the Apple Public Source License (any version) and+distribute the resulting combined work, as long as you follow the+requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the Apple Public+Source License.++This work also comes with the added permission that you may combine it with a+work licensed under the BitTorrent Open Source License (any version) and+distribute the resulting combined work, as long as you follow the+requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the BitTorrent+Open Source License.++This work also comes with the added permission that you may combine it with a+work licensed under the Lucent Public License (any version) and distribute+the resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Lucent Public License.++This work also comes with the added permission that you may combine it with a+work licensed under the Jabber Open Source License (any version) and+distribute the resulting combined work, as long as you follow the+requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the Jabber Open+Source License.++This work also comes with the added permission that you may combine it with a+work licensed under the Common Development and Distribution License (any+version) and distribute the resulting combined work, as long as you follow+the requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the Common+Development and Distribution License.++This work also comes with the added permission that you may combine it with a+work licensed under the Microsoft Public License (any version) and distribute+the resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Microsoft Public License.++This work also comes with the added permission that you may combine it with a+work licensed under the Microsoft Reciprocal License (any version) and+distribute the resulting combined work, as long as you follow the+requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the Microsoft+Reciprocal License.++This work also comes with the added permission that you may combine it with a+work licensed under the Sun Industry Standards Source License (any version)+and distribute the resulting combined work, as long as you follow the+requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the Sun Industry+Standards Source License.++This work also comes with the added permission that you may combine it with a+work licensed under the Open Software License (any version) and distribute+the resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Open Software License.+   		    GNU GENERAL PUBLIC LICENSE

@@ -1,80 +0,0 @@-<!DOCtype HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">-<html lang="en">--  <head>-    <title>transitive grace period public licence, v1.0</title>--    <link rev="made" class="mailto" href="mailto:zooko[at]zooko[dot]com">--    <link rel="stylesheet" href="style.css" type="text/css">--    <meta name="description" content="an open source licence for commercial software">-    <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">--    <meta name="keywords" content="Zooko">-  </head>--  <body>-<h1>Transitive Grace Period Public Licence ("TGPPL") v. 1.0</h1>--<p>This Transitive Grace Period Public Licence (the "License") applies to any original work of authorship (the "Original Work") whose owner (the "Licensor") has placed the following licensing notice adjacent to the copyright notice for the Original Work:</p>--<p><b>Licensed under the Transitive Grace Period Public Licence version 1.0</b></p>--<ol>-   <li><b>Grant of Copyright License.</b> Licensor grants You a worldwide, royalty-free, non-exclusive, sublicensable license, for the duration of the copyright, to do the following:</p>--     <ol type="a">-         <li>to reproduce the Original Work in copies, either alone or as part of a collective work;</p>--         <li>to translate, adapt, alter, transform, modify, or arrange the Original Work, thereby creating derivative works ("Derivative Works") based upon the Original Work;</p>--         <li>to distribute or communicate copies of the Original Work and Derivative Works to the public, with the proviso that copies of Original Work or Derivative Works that You distribute or communicate shall be licensed under this Transitive Grace Period Public Licence no later than 12 months after You distributed or communicated said copies;</p>--         <li>to perform the Original Work publicly; and</p>--         <li>to display the Original Work publicly.</p>-	   </ol>--   <li><b>Grant of Patent License.</b> Licensor grants You a worldwide, royalty-free, non-exclusive, sublicensable license, under patent claims owned or controlled by the Licensor that are embodied in the Original Work as furnished by the Licensor, for the duration of the patents, to make, use, sell, offer for sale, have made, and import the Original Work and Derivative Works.</p>--   <li><b>Grant of Source Code License.</b> The term "Source Code" means the preferred form of the Original Work for making modifications to it and all available documentation describing how to modify the Original Work. Licensor agrees to provide a machine-readable copy of the Source Code of the Original Work along with each copy of the Original Work that Licensor distributes. Licensor reserves the right to satisfy this obligation by placing a machine-readable copy of the Source Code in an information repository reasonably calculated to permit inexpensive and convenient access by You for as long as Licensor continues to distribute the Original Work.</p>--   <li><b>Exclusions From License Grant.</b> Neither the names of Licensor, nor the names of any contributors to the Original Work, nor any of their trademarks or service marks, may be used to endorse or promote products derived from this Original Work without express prior permission of the Licensor. Except as expressly stated herein, nothing in this License grants any license to Licensor's trademarks, copyrights, patents, trade secrets or any other intellectual property. No patent license is granted to make, use, sell, offer for sale, have made, or import embodiments of any patent claims other than the licensed claims defined in Section 2. No license is granted to the trademarks of Licensor even if such marks are included in the Original Work. Nothing in this License shall be interpreted to prohibit Licensor from licensing under terms different from this License any Original Work that Licensor otherwise would have a right to license.</p>--   <li><b>External Deployment.</b> The term "External Deployment" means the use, distribution, or communication of the Original Work or Derivative Works in any way such that the Original Work or Derivative Works may be used by anyone other than You, whether those works are distributed or communicated to those persons or made available as an application intended for use over a network. As an express condition for the grants of license hereunder, You must treat any External Deployment by You of the Original Work or a Derivative Work as a distribution under section 1(c).</p>--   <li><b>Attribution Rights.</b> You must retain, in the Source Code of any Derivative Works that You create, all copyright, patent, or trademark notices from the Source Code of the Original Work, as well as any notices of licensing and any descriptive text identified therein as an "Attribution Notice." You must cause the Source Code for any Derivative Works that You create to carry a prominent Attribution Notice reasonably calculated to inform recipients that You have modified the Original Work.</p>--   <li><b>Warranty of Provenance and Disclaimer of Warranty.</b> Licensor warrants that the copyright in and to the Original Work and the patent rights granted herein by Licensor are owned by the Licensor or are sublicensed to You under the terms of this License with the permission of the contributor(s) of those copyrights and patent rights. Except as expressly stated in the immediately preceding sentence, the Original Work is provided under this License on an "AS IS" BASIS and WITHOUT WARRANTY, either express or implied, including, without limitation, the warranties of non-infringement, merchantability or fitness for a particular purpose. THE ENTIRE RISK AS TO THE QUALITY OF THE ORIGINAL WORK IS WITH YOU. This DISCLAIMER OF WARRANTY constitutes an essential part of this License. No license to the Original Work is granted by this License except under this disclaimer.</p>--   <li><b>Limitation of Liability.</b> Under no circumstances and under no legal theory, whether in tort (including negligence), contract, or otherwise, shall the Licensor be liable to anyone for any indirect, special, incidental, or consequential damages of any character arising as a result of this License or the use of the Original Work including, without limitation, damages for loss of goodwill, work stoppage, computer failure or malfunction, or any and all other commercial damages or losses. This limitation of liability shall not apply to the extent applicable law prohibits such limitation.</p>--   <li><b>Acceptance and Termination.</b> If, at any time, You expressly assented to this License, that assent indicates your clear and irrevocable acceptance of this License and all of its terms and conditions. If You distribute or communicate copies of the Original Work or a Derivative Work, You must make a reasonable effort under the circumstances to obtain the express assent of recipients to the terms of this License. This License conditions your rights to undertake the activities listed in Section 1, including your right to create Derivative Works based upon the Original Work, and doing so without honoring these terms and conditions is prohibited by copyright law and international treaty. Nothing in this License is intended to affect copyright exceptions and limitations (including 'fair use' or 'fair dealing'). This License shall terminate immediately and You may no longer exercise any of the rights granted to You by this License upon your failure to honor the conditions in Section 1(c).</p>--  <li><b>Termination for Patent Action.</b> This License shall terminate automatically and You may no longer exercise any of the rights granted to You by this License as of the date You commence an action, including a cross-claim or counterclaim, against Licensor or any licensee alleging that the Original Work infringes a patent. This termination provision shall not apply for an action alleging patent infringement by combinations of the Original Work with other software or hardware.</p>--  <li><b>Jurisdiction, Venue and Governing Law.</b> Any action or suit relating to this License may be brought only in the courts of a jurisdiction wherein the Licensor resides or in which Licensor conducts its primary business, and under the laws of that jurisdiction excluding its conflict-of-law provisions. The application of the United Nations Convention on Contracts for the International Sale of Goods is expressly excluded. Any use of the Original Work outside the scope of this License or after its termination shall be subject to the requirements and penalties of copyright or patent law in the appropriate jurisdiction. This section shall survive the termination of this License.</p>--  <li><b>Attorneys' Fees.</b> In any action to enforce the terms of this License or seeking damages relating thereto, the prevailing party shall be entitled to recover its costs and expenses, including, without limitation, reasonable attorneys' fees and costs incurred in connection with such action, including any appeal of such action. This section shall survive the termination of this License.</p>--  <li><b>Miscellaneous.</b> If any provision of this License is held to be unenforceable, such provision shall be reformed only to the extent necessary to make it enforceable.</p>--  <li><b>Definition of "You" in This License.</b> "You" throughout this License, whether in upper or lower case, means an individual or a legal entity exercising rights under, and complying with all of the terms of, this License. For legal entities, "You" includes any entity that controls, is controlled by, or is under common control with you. For purposes of this definition, "control" means (i) the power, direct or indirect, to cause the direction or management of such entity, whether by contract or otherwise, or (ii) ownership of fifty percent (50%) or more of the outstanding shares, or (iii) beneficial ownership of such entity.</p>--  <li><b>Right to Use.</b> You may use the Original Work in all ways not otherwise restricted or conditioned by this License or by law, and Licensor promises not to interfere with or be responsible for such uses by You.</p>--  <li><b>Modification of This License.</b> This License is Copyright © 2007 Zooko Wilcox-O'Hearn. Permission is granted to copy, distribute, or communicate this License without modification. Nothing in this License permits You to modify this License as applied to the Original Work or to Derivative Works. However, You may modify the text of this License and copy, distribute or communicate your modified version (the "Modified License") and apply it to other original works of authorship subject to the following conditions: (i) You may not indicate in any way that your Modified License is the "Transitive Grace Period Public Licence" or "TGPPL" and you may not use those names in the name of your Modified License; and (ii) You must replace the notice specified in the first paragraph above with the notice "Licensed under <insert your license name here>" or with a notice of your own that is not confusingly similar to the notice in this License.</p>-</ol>--              </td>-             </td>-            </tr>--           </table>-          </td>-         </tr>-        </table>--  </body>-</html>

@@ -0,0 +1,291 @@+This work also comes with the added permission that you may combine it with a+work licensed under the OpenSSL license (any version) and distribute the+resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the OpenSSL license.++This work also comes with the added permission that you may combine it with a+work licensed under the Eclipse Public Licence (any version) and distribute+the resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Eclipse Public Licence.++This work also comes with the added permission that you may combine it with a+work licensed under the Q Public Licence (any version) and distribute the+resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Q Public Licence.++This work also comes with the added permission that you may combine it with a+work licensed under the Apache Licence (any version) and distribute the+resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Apache Licence.++This work also comes with the added permission that you may combine it with a+work licensed under the GNU Lesser General Public License (any version) and+distribute the resulting combined work, as long as you follow the+requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the GNU Lesser+General Public License.++This work also comes with the added permission that you may combine it with a+work licensed under the Zope Public License (any version) and distribute the+resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Zope Public License.++This work also comes with the added permission that you may combine it with a+work licensed under the Python Software Foundation License (any version) and+distribute the resulting combined work, as long as you follow the+requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the Python+Software Foundation License.++This work also comes with the added permission that you may combine it with a+work licensed under the Academic Free License (any version) and distribute+the resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Academic Free License.++This work also comes with the added permission that you may combine it with a+work licensed under the Apple Public Source License (any version) and+distribute the resulting combined work, as long as you follow the+requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the Apple Public+Source License.++This work also comes with the added permission that you may combine it with a+work licensed under the BitTorrent Open Source License (any version) and+distribute the resulting combined work, as long as you follow the+requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the BitTorrent+Open Source License.++This work also comes with the added permission that you may combine it with a+work licensed under the Lucent Public License (any version) and distribute+the resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Lucent Public License.++This work also comes with the added permission that you may combine it with a+work licensed under the Jabber Open Source License (any version) and+distribute the resulting combined work, as long as you follow the+requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the Jabber Open+Source License.++This work also comes with the added permission that you may combine it with a+work licensed under the Common Development and Distribution License (any+version) and distribute the resulting combined work, as long as you follow+the requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the Common+Development and Distribution License.++This work also comes with the added permission that you may combine it with a+work licensed under the Microsoft Public License (any version) and distribute+the resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Microsoft Public License.++This work also comes with the added permission that you may combine it with a+work licensed under the Microsoft Reciprocal License (any version) and+distribute the resulting combined work, as long as you follow the+requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the Microsoft+Reciprocal License.++This work also comes with the added permission that you may combine it with a+work licensed under the Sun Industry Standards Source License (any version)+and distribute the resulting combined work, as long as you follow the+requirements of the licences of this work in regard to all of the+resulting combined work aside from the work licensed under the Sun Industry+Standards Source License.++This work also comes with the added permission that you may combine it with a+work licensed under the Open Software License (any version) and distribute+the resulting combined work, as long as you follow the requirements of the+licences of this work in regard to all of the resulting combined work+aside from the work licensed under the Open Software License.++=======================================================+Transitive Grace Period Public Licence ("TGPPL") v. 1.0+=======================================================++This Transitive Grace Period Public Licence (the "License") applies to any+original work of authorship (the "Original Work") whose owner (the+"Licensor") has placed the following licensing notice adjacent to the+copyright notice for the Original Work:++ *Licensed under the Transitive Grace Period Public Licence version 1.0*++1.  **Grant of Copyright License.** Licensor grants You a worldwide,+    royalty-free, non-exclusive, sublicensable license, for the duration of+    the copyright, to do the following:++    a. to reproduce the Original Work in copies, either alone or as part of a+       collective work;++    b. to translate, adapt, alter, transform, modify, or arrange the Original+       Work, thereby creating derivative works ("Derivative Works") based upon+       the Original Work;++    c. to distribute or communicate copies of the Original Work and Derivative+       Works to the public, with the proviso that copies of Original Work or+       Derivative Works that You distribute or communicate shall be licensed+       under this Transitive Grace Period Public Licence no later than 12+       months after You distributed or communicated said copies;++    d. to perform the Original Work publicly; and++    e. to display the Original Work publicly.++2.  **Grant of Patent License.** Licensor grants You a worldwide,+    royalty-free, non-exclusive, sublicensable license, under patent claims+    owned or controlled by the Licensor that are embodied in the Original+    Work as furnished by the Licensor, for the duration of the patents, to+    make, use, sell, offer for sale, have made, and import the Original Work+    and Derivative Works.++3.  **Grant of Source Code License.** The term "Source Code" means the+    preferred form of the Original Work for making modifications to it and+    all available documentation describing how to modify the Original+    Work. Licensor agrees to provide a machine-readable copy of the Source+    Code of the Original Work along with each copy of the Original Work that+    Licensor distributes. Licensor reserves the right to satisfy this+    obligation by placing a machine-readable copy of the Source Code in an+    information repository reasonably calculated to permit inexpensive and+    convenient access by You for as long as Licensor continues to distribute+    the Original Work.++4.  **Exclusions From License Grant.** Neither the names of Licensor, nor the+    names of any contributors to the Original Work, nor any of their+    trademarks or service marks, may be used to endorse or promote products+    derived from this Original Work without express prior permission of the+    Licensor. Except as expressly stated herein, nothing in this License+    grants any license to Licensor's trademarks, copyrights, patents, trade+    secrets or any other intellectual property. No patent license is granted+    to make, use, sell, offer for sale, have made, or import embodiments of+    any patent claims other than the licensed claims defined in Section 2. No+    license is granted to the trademarks of Licensor even if such marks are+    included in the Original Work. Nothing in this License shall be+    interpreted to prohibit Licensor from licensing under terms different+    from this License any Original Work that Licensor otherwise would have a+    right to license.++5.  **External Deployment.** The term "External Deployment" means the use,+    distribution, or communication of the Original Work or Derivative Works+    in any way such that the Original Work or Derivative Works may be used by+    anyone other than You, whether those works are distributed or+    communicated to those persons or made available as an application+    intended for use over a network. As an express condition for the grants+    of license hereunder, You must treat any External Deployment by You of+    the Original Work or a Derivative Work as a distribution under section+    1(c).++6.  **Attribution Rights.** You must retain, in the Source Code of any+    Derivative Works that You create, all copyright, patent, or trademark+    notices from the Source Code of the Original Work, as well as any notices+    of licensing and any descriptive text identified therein as an+    "Attribution Notice." You must cause the Source Code for any Derivative+    Works that You create to carry a prominent Attribution Notice reasonably+    calculated to inform recipients that You have modified the Original Work.++7.  **Warranty of Provenance and Disclaimer of Warranty.** Licensor warrants+    that the copyright in and to the Original Work and the patent rights+    granted herein by Licensor are owned by the Licensor or are sublicensed+    to You under the terms of this License with the permission of the+    contributor(s) of those copyrights and patent rights. Except as expressly+    stated in the immediately preceding sentence, the Original Work is+    provided under this License on an "AS IS" BASIS and WITHOUT WARRANTY,+    either express or implied, including, without limitation, the warranties+    of non-infringement, merchantability or fitness for a particular+    purpose. THE ENTIRE RISK AS TO THE QUALITY OF THE ORIGINAL WORK IS WITH+    YOU. This DISCLAIMER OF WARRANTY constitutes an essential part of this+    License. No license to the Original Work is granted by this License+    except under this disclaimer.++8.  **Limitation of Liability.** Under no circumstances and under no legal+    theory, whether in tort (including negligence), contract, or otherwise,+    shall the Licensor be liable to anyone for any indirect, special,+    incidental, or consequential damages of any character arising as a result+    of this License or the use of the Original Work including, without+    limitation, damages for loss of goodwill, work stoppage, computer failure+    or malfunction, or any and all other commercial damages or losses. This+    limitation of liability shall not apply to the extent applicable law+    prohibits such limitation.++9.  **Acceptance and Termination.** If, at any time, You expressly assented+    to this License, that assent indicates your clear and irrevocable+    acceptance of this License and all of its terms and conditions. If You+    distribute or communicate copies of the Original Work or a Derivative+    Work, You must make a reasonable effort under the circumstances to obtain+    the express assent of recipients to the terms of this License. This+    License conditions your rights to undertake the activities listed in+    Section 1, including your right to create Derivative Works based upon the+    Original Work, and doing so without honoring these terms and conditions+    is prohibited by copyright law and international treaty. Nothing in this+    License is intended to affect copyright exceptions and limitations+    (including 'fair use' or 'fair dealing'). This License shall terminate+    immediately and You may no longer exercise any of the rights granted to+    You by this License upon your failure to honor the conditions in Section+    1(c).++10. **Termination for Patent Action.** This License shall terminate+    automatically and You may no longer exercise any of the rights granted to+    You by this License as of the date You commence an action, including a+    cross-claim or counterclaim, against Licensor or any licensee alleging+    that the Original Work infringes a patent. This termination provision+    shall not apply for an action alleging patent infringement by+    combinations of the Original Work with other software or hardware.++11. **Jurisdiction, Venue and Governing Law.** Any action or suit relating to+    this License may be brought only in the courts of a jurisdiction wherein+    the Licensor resides or in which Licensor conducts its primary business,+    and under the laws of that jurisdiction excluding its conflict-of-law+    provisions. The application of the United Nations Convention on Contracts+    for the International Sale of Goods is expressly excluded. Any use of the+    Original Work outside the scope of this License or after its termination+    shall be subject to the requirements and penalties of copyright or patent+    law in the appropriate jurisdiction. This section shall survive the+    termination of this License.++12. **Attorneys' Fees.** In any action to enforce the terms of this License+    or seeking damages relating thereto, the prevailing party shall be+    entitled to recover its costs and expenses, including, without+    limitation, reasonable attorneys' fees and costs incurred in connection+    with such action, including any appeal of such action. This section shall+    survive the termination of this License.++13. **Miscellaneous.** If any provision of this License is held to be+    unenforceable, such provision shall be reformed only to the extent+    necessary to make it enforceable.++14. **Definition of "You" in This License.** "You" throughout this License,+    whether in upper or lower case, means an individual or a legal entity+    exercising rights under, and complying with all of the terms of, this+    License. For legal entities, "You" includes any entity that controls, is+    controlled by, or is under common control with you. For purposes of this+    definition, "control" means (i) the power, direct or indirect, to cause+    the direction or management of such entity, whether by contract or+    otherwise, or (ii) ownership of fifty percent (50%) or more of the+    outstanding shares, or (iii) beneficial ownership of such entity.++15. **Right to Use.** You may use the Original Work in all ways not otherwise+    restricted or conditioned by this License or by law, and Licensor+    promises not to interfere with or be responsible for such uses by You.++16. **Modification of This License.** This License is Copyright © 2007 Zooko+    Wilcox-O'Hearn. Permission is granted to copy, distribute, or communicate+    this License without modification. Nothing in this License permits You to+    modify this License as applied to the Original Work or to Derivative+    Works. However, You may modify the text of this License and copy,+    distribute or communicate your modified version (the "Modified License")+    and apply it to other original works of authorship subject to the+    following conditions: (i) You may not indicate in any way that your+    Modified License is the "Transitive Grace Period Public Licence" or+    "TGPPL" and you may not use those names in the name of your Modified+    License; and (ii) You must replace the notice specified in the first+    paragraph above with the notice "Licensed under <insert your license name+    here>" or with a notice of your own that is not confusingly similar to+    the notice in this License.

@@ -0,0 +1,10 @@+# Changelog for fec++## 0.2.0 (2023-10-06)++* Application code must now execute the `Codec.FEC.initialize` action at least+  once before using other `Codec.FEC` APIs.++* `Codec.FEC.fec`, `Codec.FEC.encode`, and `Codec.FEC.decode` are now thread-safe.++* `Codec.FEC.fec` now supports n == k.

@@ -0,0 +1,327 @@+++zfec -- efficient, portable erasure coding tool+===============================================++Generate redundant blocks of information such that if some of the blocks are+lost then the original data can be recovered from the remaining blocks. This+package includes command-line tools, C API, Python API, and Haskell API.++|build| |test| |pypi|++Intro and Licence+-----------------++This package implements an "erasure code", or "forward error correction+code".++You may use this package under the GNU General Public License, version 2 or,+at your option, any later version.  You may use this package under the+Transitive Grace Period Public Licence, version 1.0 or, at your option, any+later version.  (You may choose to use this package under the terms of either+licence, at your option.)  See the file COPYING.GPL for the terms of the GNU+General Public License, version 2.  See the file COPYING.TGPPL.rst for the+terms of the Transitive Grace Period Public Licence, version 1.0.++The most widely known example of an erasure code is the RAID-5 algorithm+which makes it so that in the event of the loss of any one hard drive, the+stored data can be completely recovered.  The algorithm in the zfec package+has a similar effect, but instead of recovering from the loss of only a+single element, it can be parameterized to choose in advance the number of+elements whose loss it can tolerate.++This package is largely based on the old "fec" library by Luigi Rizzo et al.,+which is a mature and optimized implementation of erasure coding.  The zfec+package makes several changes from the original "fec" package, including+addition of the Python API, refactoring of the C API to support zero-copy+operation, a few clean-ups and optimizations of the core code itself, and the+addition of a command-line tool named "zfec".+++Installation+------------++``pip install zfec``++To run the self-tests, execute ``tox`` from an unpacked source tree or git checkout.++To run the tests of the Haskell API: ``cabal run test:tests``+++Community+---------++The source is currently available via git on the web with the command:++``git clone https://github.com/tahoe-lafs/zfec``++Please post about zfec to the Tahoe-LAFS mailing list and contribute patches:++<https://tahoe-lafs.org/cgi-bin/mailman/listinfo/tahoe-dev>++If you find a bug in zfec, please open an issue on github:++<https://github.com/tahoe-lafs/zfec/issues>++Overview+--------++This package performs two operations, encoding and decoding.  Encoding takes+some input data and expands its size by producing extra "check blocks", also+called "secondary blocks".  Decoding takes some data -- any combination of+blocks of the original data (called "primary blocks") and "secondary blocks",+and produces the original data.++The encoding is parameterized by two integers, k and m.  m is the total+number of blocks produced, and k is how many of those blocks are necessary to+reconstruct the original data.  m is required to be at least 1 and at most+256, and k is required to be at least 1 and at most m.++(Note that when k == m then there is no point in doing erasure coding -- it+degenerates to the equivalent of the Unix "split" utility which simply splits+the input into successive segments.  Similarly, when k == 1 it degenerates to+the equivalent of the unix "cp" utility -- each block is a complete copy of+the input data.)++Note that each "primary block" is a segment of the original data, so its size+is 1/k'th of the size of original data, and each "secondary block" is of the+same size, so the total space used by all the blocks is m/k times the size of+the original data (plus some padding to fill out the last primary block to be+the same size as all the others).  In addition to the data contained in the+blocks themselves there are also a few pieces of metadata which are necessary+for later reconstruction.  Those pieces are: 1.  the value of K, 2.  the+value of M, 3.  the sharenum of each block, 4.  the number of bytes of+padding that were used.  The "zfec" command-line tool compresses these pieces+of data and prepends them to the beginning of each share, so each the+sharefile produced by the "zfec" command-line tool is between one and four+bytes larger than the share data alone.++The decoding step requires as input k of the blocks which were produced by+the encoding step.  The decoding step produces as output the data that was+earlier input to the encoding step.+++Command-Line Tool+-----------------++The bin/ directory contains two Unix-style, command-line tools "zfec" and+"zunfec".  Execute ``zfec --help`` or ``zunfec --help`` for usage+instructions.+++Performance+-----------++To run the benchmarks, execute the included bench/bench_zfec.py script with+optional --k= and --m= arguments.++On my Athlon 64 2.4 GHz workstation (running Linux), the "zfec" command-line+tool encoded a 160 MB file with m=100, k=94 (about 6% redundancy) in 3.9+seconds, where the "par2" tool encoded the file with about 6% redundancy in+27 seconds.  zfec encoded the same file with m=12, k=6 (100% redundancy) in+4.1 seconds, where par2 encoded it with about 100% redundancy in 7 minutes+and 56 seconds.++The underlying C library in benchmark mode encoded from a file at about 4.9+million bytes per second and decoded at about 5.8 million bytes per second.++On Peter's fancy Intel Mac laptop (2.16 GHz Core Duo), it encoded from a file+at about 6.2 million bytes per second.++On my even fancier Intel Mac laptop (2.33 GHz Core Duo), it encoded from a+file at about 6.8 million bytes per second.++On my old PowerPC G4 867 MHz Mac laptop, it encoded from a file at about 1.3+million bytes per second.++Here is a paper analyzing the performance of various erasure codes and their+implementations, including zfec:++http://www.usenix.org/events/fast09/tech/full_papers/plank/plank.pdf++Zfec shows good performance on different machines and with different values+of K and M. It also has a nice small memory footprint.+++API+---++Each block is associated with "blocknum".  The blocknum of each primary block+is its index (starting from zero), so the 0'th block is the first primary+block, which is the first few bytes of the file, the 1'st block is the next+primary block, which is the next few bytes of the file, and so on.  The last+primary block has blocknum k-1.  The blocknum of each secondary block is an+arbitrary integer between k and 255 inclusive.  (When using the Python API,+if you don't specify which secondary blocks you want when invoking encode(),+then it will by default provide the blocks with ids from k to m-1 inclusive.)++- C API++  fec_encode() takes as input an array of k pointers, where each pointer+  points to a memory buffer containing the input data (i.e., the i'th buffer+  contains the i'th primary block).  There is also a second parameter which+  is an array of the blocknums of the secondary blocks which are to be+  produced.  (Each element in that array is required to be the blocknum of a+  secondary block, i.e. it is required to be >= k and < m.)++  The output from fec_encode() is the requested set of secondary blocks which+  are written into output buffers provided by the caller.++  Note that this fec_encode() is a "low-level" API in that it requires the+  input data to be provided in a set of memory buffers of exactly the right+  sizes.  If you are starting instead with a single buffer containing all of+  the data then please see easyfec.py's "class Encoder" as an example of how+  to split a single large buffer into the appropriate set of input buffers+  for fec_encode().  If you are starting with a file on disk, then please see+  filefec.py's encode_file_stringy_easyfec() for an example of how to read+  the data from a file and pass it to "class Encoder".  The Python interface+  provides these higher-level operations, as does the Haskell interface.  If+  you implement functions to do these higher-level tasks in other languages,+  please send a patch to tahoe-dev@tahoe-lafs.org so that your API can be+  included in future releases of zfec.++  fec_decode() takes as input an array of k pointers, where each pointer+  points to a buffer containing a block.  There is also a separate input+  parameter which is an array of blocknums, indicating the blocknum of each+  of the blocks which is being passed in.++  The output from fec_decode() is the set of primary blocks which were+  missing from the input and had to be reconstructed.  These reconstructed+  blocks are written into output buffers provided by the caller.+++- Python API++  encode() and decode() take as input a sequence of k buffers, where a+  "sequence" is any object that implements the Python sequence protocol (such+  as a list or tuple) and a "buffer" is any object that implements the Python+  buffer protocol (such as a string or array).  The contents that are+  required to be present in these buffers are the same as for the C API.++  encode() also takes a list of desired blocknums.  Unlike the C API, the+  Python API accepts blocknums of primary blocks as well as secondary blocks+  in its list of desired blocknums.  encode() returns a list of buffer+  objects which contain the blocks requested.  For each requested block which+  is a primary block, the resulting list contains a reference to the+  apppropriate primary block from the input list.  For each requested block+  which is a secondary block, the list contains a newly created string object+  containing that block.++  decode() also takes a list of integers indicating the blocknums of the+  blocks being passed int.  decode() returns a list of buffer objects which+  contain all of the primary blocks of the original data (in order).  For+  each primary block which was present in the input list, then the result+  list simply contains a reference to the object that was passed in the input+  list.  For each primary block which was not present in the input, the+  result list contains a newly created string object containing that primary+  block.++  Beware of a "gotcha" that can result from the combination of mutable data+  and the fact that the Python API returns references to inputs when+  possible.++  Returning references to its inputs is efficient since it avoids making an+  unnecessary copy of the data, but if the object which was passed as input+  is mutable and if that object is mutated after the call to zfec returns,+  then the result from zfec -- which is just a reference to that same object+  -- will also be mutated.  This subtlety is the price you pay for avoiding+  data copying.  If you don't want to have to worry about this then you can+  simply use immutable objects (e.g. Python strings) to hold the data that+  you pass to zfec.++- Haskell API++  The Haskell code is fully Haddocked, to generate the documentation, run+  ``runhaskell Setup.lhs haddock``.+++Utilities+---------++The filefec.py module has a utility function for efficiently reading a file+and encoding it piece by piece.  This module is used by the "zfec" and+"zunfec" command-line tools from the bin/ directory.+++Dependencies+------------++A C compiler is required.  To use the Python API or the command-line tools a+Python interpreter is also required.  We have tested it with Python v2.7,+v3.5 and v3.6.  For the Haskell interface, GHC >= 6.8.1 is required.+++Acknowledgements+----------------++Thanks to the author of the original fec lib, Luigi Rizzo, and the folks that+contributed to it: Phil Karn, Robert Morelos-Zaragoza, Hari Thirumoorthy, and+Dan Rubenstein.  Thanks to the Mnet hackers who wrote an earlier Python+wrapper, especially Myers Carpenter and Hauke Johannknecht.  Thanks to Brian+Warner and Amber O'Whielacronx for help with the API, documentation,+debugging, compression, and unit tests.  Thanks to Adam Langley for improving+the C API and contributing the Haskell API.  Thanks to the creators of GCC+(starting with Richard M. Stallman) and Valgrind (starting with Julian+Seward) for a pair of excellent tools.  Thanks to my coworkers at Allmydata+-- http://allmydata.com -- Fabrice Grinda, Peter Secor, Rob Kinninmont, Brian+Warner, Zandr Milewski, Justin Boreta, Mark Meras for sponsoring this work+and releasing it under a Free Software licence. Thanks to Jack Lloyd, Samuel+Neves, and David-Sarah Hopwood.+++Related Works+-------------++Note: a Unix-style tool like "zfec" does only one thing -- in this case+erasure coding -- and leaves other tasks to other tools.  Other Unix-style+tools that go well with zfec include `GNU tar`_ for archiving multiple files+and directories into one file, `lzip`_ for compression, and `GNU Privacy+Guard`_ for encryption or `b2sum`_ for integrity.  It is important to do+things in order: first archive, then compress, then either encrypt or+integrity-check, then erasure code.  Note that if GNU Privacy Guard is used+for privacy, then it will also ensure integrity, so the use of b2sum is+unnecessary in that case. Note also that you also need to do integrity+checking (such as with b2sum) on the blocks that result from the erasure+coding in *addition* to doing it on the file contents! (There are two+different subtle failure modes -- see "more than one file can match an+immutable file cap" on the `Hack Tahoe-LAFS!`_ Hall of Fame.)++The `Tahoe-LAFS`_ project uses zfec as part of a complete distributed+filesystem with integrated encryption, integrity, remote distribution of the+blocks, directory structure, backup of changed files or directories, access+control, immutable files and directories, proof-of-retrievability, and repair+of damaged files and directories.++`fecpp`_ is an alternative to zfec. It implements a bitwise-compatible+algorithm to zfec and is BSD-licensed.++.. _GNU tar: http://directory.fsf.org/project/tar/+.. _lzip: http://www.nongnu.org/lzip/lzip.html+.. _GNU Privacy Guard: http://gnupg.org/+.. _b2sum: https://blake2.net/+.. _Tahoe-LAFS: https://tahoe-lafs.org+.. _Hack Tahoe-LAFS!: https://tahoe-lafs.org/hacktahoelafs/+.. _fecpp: http://www.randombit.net/code/fecpp/+++Enjoy!++Zooko Wilcox-O'Hearn++2013-05-15++Boulder, Colorado++----++.. |pypi| image:: http://img.shields.io/pypi/v/zfec.svg+   :alt: PyPI release status+   :target: https://pypi.python.org/pypi/zfec++.. |build| image:: https://github.com/tahoe-lafs/zfec/actions/workflows/build.yml/badge.svg+   :alt: Package Build+   :target: https://github.com/tahoe-lafs/zfec/actions/workflows/build.yml++.. |test| image:: https://github.com/tahoe-lafs/zfec/actions/workflows/test.yml/badge.svg+   :alt: Tests+   :target: https://github.com/tahoe-lafs/zfec/actions/workflows/test.yml

@@ -1,252 +0,0 @@- * Intro and Licence--This package implements an "erasure code", or "forward error correction code".--You may use this package under the GNU General Public License, version 2 or, at-your option, any later version.  You may use this package under the Transitive-Grace Period Public Licence, version 1.0.  (You may choose to use this package-under the terms of either licence, at your option.)  See the file COPYING.GPL-for the terms of the GNU General Public License, version 2.  See the file-COPYING.TGPPL.html for the terms of the Transitive Grace Period Public Licence,-version 1.0.--The most widely known example of an erasure code is the RAID-5 algorithm which-makes it so that in the event of the loss of any one hard drive, the stored data-can be completely recovered.  The algorithm in the zfec package has a similar-effect, but instead of recovering from the loss of only a single element, it can-be parameterized to choose in advance the number of elements whose loss it can-tolerate.--This package is largely based on the old "fec" library by Luigi Rizzo et al.,-which is a mature and optimized implementation of erasure coding.  The zfec-package makes several changes from the original "fec" package, including-addition of the Python API, refactoring of the C API to support zero-copy-operation, a few clean-ups and optimizations of the core code itself, and the-addition of a command-line tool named "zfec".--- * Installation--This package is managed with the "setuptools" package management tool.  To build-and install the package directly into your system, just run "python ./setup.py-install".  If you prefer to keep the package limited to a specific directory so-that you can manage it yourself (perhaps by using the "GNU stow") tool, then-give it these arguments: "python ./setup.py install---single-version-externally-managed---record=${specificdirectory}/zfec-install.log --prefix=${specificdirectory}"--To run the self-tests, execute "python ./setup.py test" (or if you have Twisted-Python installed, you can run "trial zfec" for nicer output and test options.)-This will run the tests of the C API, the Python API, and the command-line-tools.--To run the tests of the Haskell API:-  % runhaskell haskell/test/FECTest.hs--Note that you must have installed the library first in order for this to work-due to the fact that the interpreter cannot process FEC.hs as it takes a-reference to an FFI function.---- * Community--The source is currently available via darcs on the web with the command:--darcs get http://allmydata.org/source/zfec--More information on darcs is available at http://darcs.net--Please join the zfec mailing list and submit patches:--<http://allmydata.org/cgi-bin/mailman/listinfo/zfec-dev>--- * Overview--This package performs two operations, encoding and decoding.  Encoding takes-some input data and expands its size by producing extra "check blocks", also-called "secondary blocks".  Decoding takes some data -- any combination of-blocks of the original data (called "primary blocks") and "secondary blocks",-and produces the original data.--The encoding is parameterized by two integers, k and m.  m is the total number-of blocks produced, and k is how many of those blocks are necessary to-reconstruct the original data.  m is required to be at least 1 and at most 256,-and k is required to be at least 1 and at most m.--(Note that when k == m then there is no point in doing erasure coding -- it-degenerates to the equivalent of the Unix "split" utility which simply splits-the input into successive segments.  Similarly, when k == 1 it degenerates to-the equivalent of the unix "cp" utility -- each block is a complete copy of the-input data.  The "zfec" command-line tool does not implement these degenerate-cases.)--Note that each "primary block" is a segment of the original data, so its size is-1/k'th of the size of original data, and each "secondary block" is of the same-size, so the total space used by all the blocks is m/k times the size of the-original data (plus some padding to fill out the last primary block to be the-same size as all the others).  In addition to the data contained in the blocks-themselves there are also a few pieces of metadata which are necessary for later-reconstruction.  Those pieces are: 1.  the value of K, 2.  the value of M, 3.-the sharenum of each block, 4.  the number of bytes of padding that were used.-The "zfec" command-line tool compresses these pieces of data and prepends them-to the beginning of each share, so each the sharefile produced by the "zfec"-command-line tool is between one and four bytes larger than the share data-alone.--The decoding step requires as input k of the blocks which were produced by the-encoding step.  The decoding step produces as output the data that was earlier-input to the encoding step.--- * Command-Line Tool--NOTE: the format of the sharefiles was changed in zfec v1.1 to allow K == 1 and-K == M.  This change of the format of sharefiles means that zfec >= v1.1 cannot-read sharefiles produced by zfec < v1.1.--The bin/ directory contains two Unix-style, command-line tools "zfec" and-"zunfec".  Execute "zfec --help" or "zunfec --help" for usage instructions.--Note: a Unix-style tool like "zfec" does only one thing -- in this case erasure-coding -- and leaves other tasks to other tools.  Other Unix-style tools that go-well with zfec include "GNU tar" for archiving multiple files and directories-into one file, "rzip" or "lrzip" for compression, and "GNU Privacy Guard" for-encryption or "sha256sum" for integrity.  It is important to do things in order:-first archive, then compress, then either encrypt or sha256sum, then erasure-code.  Note that if GNU Privacy Guard is used for privacy, then it will also-ensure integrity, so the use of sha256sum is unnecessary in that case.--- * Performance Measurements--On my Athlon 64 2.4 GHz workstation (running Linux), the "zfec" command-line-tool encoded a 160 MB file with m=100, k=94 (about 6% redundancy) in 3.9-seconds, where the "par2" tool encoded the file with about 6% redundancy in 27-seconds.  zfec encoded the same file with m=12, k=6 (100% redundancy) in 4.1-seconds, where par2 encoded it with about 100% redundancy in 7 minutes and 56-seconds.--The underlying C library in benchmark mode encoded from a file at about 4.9-million bytes per second and decoded at about 5.8 million bytes per second.--On Peter's fancy Intel Mac laptop (2.16 GHz Core Duo), it encoded from a file at-about 6.2 million bytes per second.--On my even fancier Intel Mac laptop (2.33 GHz Core Duo), it encoded from a file-at about 6.8 million bytes per second.--On my old PowerPC G4 867 MHz Mac laptop, it encoded from a file at about 1.3-million bytes per second.--- * API--Each block is associated with "blocknum".  The blocknum of each primary block is-its index (starting from zero), so the 0'th block is the first primary block,-which is the first few bytes of the file, the 1'st block is the next primary-block, which is the next few bytes of the file, and so on.  The last primary-block has blocknum k-1.  The blocknum of each secondary block is an arbitrary-integer between k and 255 inclusive.  (When using the Python API, if you don't-specify which blocknums you want for your secondary blocks when invoking-encode(), then it will by default provide the blocks with ids from k to m-1-inclusive.)-- ** C API--fec_encode() takes as input an array of k pointers, where each pointer points to-a memory buffer containing the input data (i.e., the i'th buffer contains the-i'th primary block).  There is also a second parameter which is an array of the-blocknums of the secondary blocks which are to be produced.  (Each element in-that array is required to be the blocknum of a secondary block, i.e. it is-required to be >= k and < m.)--The output from fec_encode() is the requested set of secondary blocks which are-written into output buffers provided by the caller.--fec_decode() takes as input an array of k pointers, where each pointer points to-a buffer containing a block.  There is also a separate input parameter which is-an array of blocknums, indicating the blocknum of each of the blocks which is-being passed in.--The output from fec_decode() is the set of primary blocks which were missing-from the input and had to be reconstructed.  These reconstructed blocks are-written into output buffers provided by the caller.-- ** Python API--encode() and decode() take as input a sequence of k buffers, where a "sequence"-is any object that implements the Python sequence protocol (such as a list or-tuple) and a "buffer" is any object that implements the Python buffer protocol-(such as a string or array).  The contents that are required to be present in-these buffers are the same as for the C API.--encode() also takes a list of desired blocknums.  Unlike the C API, the Python-API accepts blocknums of primary blocks as well as secondary blocks in its list-of desired blocknums.  encode() returns a list of buffer objects which contain-the blocks requested.  For each requested block which is a primary block, the-resulting list contains a reference to the apppropriate primary block from the-input list.  For each requested block which is a secondary block, the list-contains a newly created string object containing that block.--decode() also takes a list of integers indicating the blocknums of the blocks-being passed int.  decode() returns a list of buffer objects which contain all-of the primary blocks of the original data (in order).  For each primary block-which was present in the input list, then the result list simply contains a-reference to the object that was passed in the input list.  For each primary-block which was not present in the input, the result list contains a newly-created string object containing that primary block.--Beware of a "gotcha" that can result from the combination of mutable data and-the fact that the Python API returns references to inputs when possible.--Returning references to its inputs is efficient since it avoids making an-unnecessary copy of the data, but if the object which was passed as input is-mutable and if that object is mutated after the call to zfec returns, then the-result from zfec -- which is just a reference to that same object -- will also-be mutated.  This subtlety is the price you pay for avoiding data copying.  If-you don't want to have to worry about this then you can simply use immutable-objects (e.g. Python strings) to hold the data that you pass to zfec.-- ** Haskell API--The Haskell code is fully Haddocked, to generate the documentation, run-  % runhaskell Setup.lhs haddock--- * Utilities--The filefec.py module has a utility function for efficiently reading a file and-encoding it piece by piece.  This module is used by the "zfec" and "zunfec"-command-line tools from the bin/ directory.--- * Dependencies--A C compiler is required.  To use the Python API or the command-line tools a-Python interpreter is also required.  We have tested it with Python v2.4 and-v2.5.  For the Haskell interface, GHC >= 6.8.1 is required.--- * Acknowledgements--Thanks to the author of the original fec lib, Luigi Rizzo, and the folks that-contributed to it: Phil Karn, Robert Morelos-Zaragoza, Hari Thirumoorthy, and-Dan Rubenstein.  Thanks to the Mnet hackers who wrote an earlier Python wrapper,-especially Myers Carpenter and Hauke Johannknecht.  Thanks to Brian Warner and-Amber O'Whielacronx for help with the API, documentation, debugging,-compression, and unit tests.  Thanks to Adam Langley for improving the C API and-contributing the Haskell API.  Thanks to the creators of GCC (starting with-Richard M. Stallman) and Valgrind (starting with Julian Seward) for a pair of-excellent tools.  Thanks to my coworkers at Allmydata -- http://allmydata.com ---Fabrice Grinda, Peter Secor, Rob Kinninmont, Brian Warner, Zandr Milewski,-Justin Boreta, Mark Meras for sponsoring this work and releasing it under a Free-Software licence.---Enjoy!--Zooko Wilcox-O'Hearn-2008-01-20-Boulder, Colorado

@@ -1,3 +0,0 @@-#!/usr/bin/env runhaskell-> import Distribution.Simple-> main = defaultMain

@@ -0,0 +1,93 @@+module Main where++import Codec.FEC (FECParams (paramK, paramN), decode, encode, fec, initialize)+import Control.Monad (replicateM)+import Criterion.Main (Benchmark, bench, bgroup, defaultMain, env, nf)+import Data.Bifunctor (bimap)+import qualified Data.ByteString as B+import Data.List (unfoldr)+import System.Random (genByteString, mkStdGen)++main :: IO ()+main =+    defaultMain+        -- Run against some somewhat arbitrarily chosen configurations.  Notably,+        -- though, 94/100 matches the numbers recorded in the readme.+        [ env (setupFEC 2 3) makeFECBenchmarks+        , env (setupFEC 16 31) makeFECBenchmarks+        , env (setupFEC 94 100) makeFECBenchmarks+        ]+  where+    setupFEC :: Int -> Int -> IO FECParams+    setupFEC k n = do+        initialize+        pure (fec k n)++    makeFECBenchmarks = fecGroup [10 ^ 6]++    fecGroup sizes params =+        bgroup+            (show (paramK params) <> "/" <> show (paramN params))+            ( []+                ++ (decodePrimaryBenchmark params <$> sizes)+                ++ (decodeSecondaryBenchmark params <$> sizes)+                ++ (encodeBenchmark params <$> sizes)+            )++    encodeBenchmark params size =+        env (setupBlocks (paramK params) size) $+            benchmarkEncode params+    decodePrimaryBenchmark params size =+        env (setupBlocks (paramK params) size) $+            benchmarkPrimaryDecode params+    decodeSecondaryBenchmark params size =+        env (setupBlocks (paramK params) size) $+            benchmarkSecondaryDecode params++    setupBlocks :: Int -> Int -> IO [B.ByteString]+    setupBlocks k blockSize = pure $ makeBlocks k blockSize++    benchmarkEncode params blocks =+        bench ("encode blockSize=" <> showWithUnit (B.length $ head blocks)) $+            -- We choose normal form here because the typical thing to do with the+            -- result is serialize use all of the bytes (eg, to write them to a+            -- file or send them over the network) so they will certainly all be+            -- used.+            nf (uncurry encode) (params, blocks)++    benchmarkPrimaryDecode params blocks =+        bench ("decode [0..] blockSize=" <> showWithUnit (B.length $ head blocks)) $+            -- normal form here for the same reason as in benchmarkEncode.+            -- assign block numbers to use only primary blocks+            nf (uncurry decode) (params, (zip [0 ..] blocks))++    benchmarkSecondaryDecode params blocks =+        bench ("decode [" <> show n <> "..] blockSize=" <> showWithUnit (B.length $ head blocks)) $+            -- normal form here for the same reason as in benchmarkEncode.+            -- assign block numbers to use as many non-primary blocks as+            -- possible+            nf (uncurry decode) (params, (zip [n ..] blocks))+      where+        n = paramN params - paramK params++makeBlocks :: Int -> Int -> [B.ByteString]+makeBlocks k size = take k . go $ mkStdGen 42+  where+    go = uncurry ($) . bimap (:) go . genByteString size++data BytesUnit = B | KB | MB deriving (Eq, Ord, Enum, Show, Bounded)++bestUnit :: Int -> BytesUnit+bestUnit n+    | n < 1000 = minBound+    | maxBound == nextUnit = nextUnit+    | otherwise = succ nextUnit+  where+    nextUnit = bestUnit . (`div` 1000) $ n++showWithUnit :: Int -> String+showWithUnit n = show (scale n) <> show u+  where+    scale n = n `div` (10 ^ (3 * fromEnum u))++    u = bestUnit n

@@ -1,30 +1,77 @@-name:            fec-version:         0.1.1-license:         GPL-license-file:    README.txt-author:          Adam Langley <agl@imperialviolet.org>-maintainer:      Adam Langley <agl@imperialviolet.org>-description:     This code, based on zfec by Zooko, based on code by Luigi-		 Rizzo implements an erasure code, or forward error-		 correction code. The most widely known example of an erasure-		 code is the RAID-5 algorithm which makes it so that in the-		 event of the loss of any one hard drive, the stored data can-		 be completely recovered.  The algorithm in the zfec package-		 has a similar effect, but instead of recovering from the loss-		 of only a single element, it can be parameterized to choose in-		 advance the number of elements whose loss it can tolerate.-build-type:      Simple-homepage:        http://allmydata.org/source/zfec-synopsis:        Forward error correction of ByteStrings-category:        Codec-build-depends:   base, bytestring>=0.9-stability:       provisional-tested-with:     GHC == 6.8.2-exposed-modules: Codec.FEC-extensions:      ForeignFunctionInterface-hs-source-dirs:  haskell-ghc-options:     -Wall-c-sources:       zfec/fec.c-cc-options:      -std=c99-include-dirs:    zfec-extra-source-files: zfec/fec.h, COPYING.GPL, COPYING.TGPPL.html+cabal-version:      3.0+name:               fec+version:            0.2.0+license:            GPL-2.0-or-later+license-file:       README.rst+author:             Adam Langley <agl@imperialviolet.org>+maintainer:         Adam Langley <agl@imperialviolet.org>+description:+  This code, based on zfec by Zooko, based on code by Luigi+  Rizzo implements an erasure code, or forward error+  correction code. The most widely known example of an erasure+  code is the RAID-5 algorithm which makes it so that in the+  event of the loss of any one hard drive, the stored data can+  be completely recovered.  The algorithm in the zfec package+  has a similar effect, but instead of recovering from the loss+  of only a single element, it can be parameterized to choose in+  advance the number of elements whose loss it can tolerate.++build-type:         Simple+homepage:           https://github.com/tahoe-lafs/zfec+synopsis:           Forward error correction of ByteStrings+category:           Codec+stability:          provisional+tested-with:        GHC ==8.10.7+extra-source-files:+  COPYING.GPL+  COPYING.TGPPL.rst+  zfec/fec.h++extra-doc-files:    ChangeLog.md++library+  build-depends:+    , base        >=4.9  && <5+    , bytestring  >=0.10 && <0.13+    , deepseq     >=1.4  && <1.6+    , extra       >=1.7  && <1.8++  exposed-modules:    Codec.FEC+  default-language:   Haskell2010+  default-extensions: ForeignFunctionInterface+  hs-source-dirs:     haskell+  ghc-options:        -Wall+  c-sources:          zfec/fec.c+  cc-options:         -std=c99+  include-dirs:       zfec++executable benchmark-zfec+  main-is:          Main.hs+  ghc-options:      -threaded+  build-depends:+    , base        >=4.9  && <5+    , bytestring  >=0.10 && <0.13+    , criterion   >=1.1  && <1.7+    , fec+    , random      >=1.1  && <1.3++  hs-source-dirs:   benchmark-zfec+  default-language: Haskell2010++test-suite tests+  type:             exitcode-stdio-1.0+  main-is:          FECTest.hs+  other-modules:+  hs-source-dirs:   haskell/test+  ghc-options:      -Wall -threaded -rtsopts -with-rtsopts=-N+  build-depends:+    , base                  >=4.9  && <5+    , bytestring            >=0.10 && <0.13+    , data-serializer       >=0.3  && <0.4+    , fec+    , hspec                 >=2.7  && <2.12+    , QuickCheck            >=2.14 && <2.15+    , quickcheck-instances  >=0.3  && <0.4+    , random                >=1.1  && <1.3++  default-language: Haskell2010

@@ -1,246 +1,404 @@-{-# LANGUAGE ForeignFunctionInterface, EmptyDataDecls #-}--- |--- Module:    Codec.FEC--- Copyright: Adam Langley--- License:   BSD3------ Stability: experimental------ The module provides k of n encoding - a way to generate (n - k) secondary--- blocks of data from k primary blocks such that any k blocks (primary or--- secondary) are sufficient to regenerate all blocks.------ All blocks must be the same length and you need to keep track of which--- blocks you have in order to tell decode. By convention, the blocks are--- numbered 0..(n - 1) and blocks numbered < k are the primary blocks.+{-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE EmptyDataDecls #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE ForeignFunctionInterface #-}+{-# LANGUAGE NamedFieldPuns #-} +{- |+ Module:    Codec.FEC+ Copyright: Adam Langley+ License:   GPLv2+|TGPPLv1+ (see README.rst for details)++ Stability: experimental++ The module provides k of n encoding - a way to generate (n - k) secondary+ blocks of data from k primary blocks such that any k blocks (primary or+ secondary) are sufficient to regenerate all blocks.++ All blocks must be the same length and you need to keep track of which+ blocks you have in order to tell decode. By convention, the blocks are+ numbered 0..(n - 1) and blocks numbered < k are the primary blocks.+-} module Codec.FEC (-    FECParams-  , fec-  , encode-  , decode+    FECParams (paramK, paramN),+    initialize,+    fec,+    encode,+    decode, -  -- * Utility functions-  , secureDivide-  , secureCombine-  , enFEC-  , deFEC-  ) where+    -- * Utility functions+    secureDivide,+    secureCombine,+    enFEC,+    deFEC,+) where +import Control.Concurrent.Extra (Lock, newLock, withLock)+import Control.DeepSeq (NFData (rnf))+import Control.Exception (Exception, throwIO)+import Data.Bits (xor) import qualified Data.ByteString as B import qualified Data.ByteString.Unsafe as BU-import qualified Data.ByteString.Internal as BI+import Data.List (nub, partition, sortBy, (\\)) import Data.Word (Word8)-import Data.Bits (xor)-import Data.List (sortBy, partition, (\\), nub)-import Foreign.Ptr-import Foreign.Storable (sizeOf, poke)-import Foreign.ForeignPtr-import Foreign.C.Types-import Foreign.Marshal.Alloc-import Foreign.Marshal.Array (withArray, advancePtr)-import System.IO (withFile, IOMode(..))+import Foreign.C.Types (CSize (..), CUInt (..))+import Foreign.ForeignPtr (+    ForeignPtr,+    newForeignPtr,+    withForeignPtr,+ )+import Foreign.Marshal.Alloc (allocaBytes)+import Foreign.Marshal.Array (advancePtr, withArray)+import Foreign.Ptr (FunPtr, Ptr, castPtr, nullPtr)+import Foreign.Storable (poke, sizeOf)+import GHC.Generics (Generic)+import System.IO (IOMode (..), withFile) import System.IO.Unsafe (unsafePerformIO)  data CFEC-data FECParams = FECParams (ForeignPtr CFEC) Int Int+data FECParams = FECParams+    { _cfec :: !(ForeignPtr CFEC)+    , paramK :: Int+    , paramN :: Int+    }+    deriving (Generic) +-- Provide an NFData instance so it's possible to use a FECParams in a+-- Criterion benchmark.+instance NFData FECParams where+    rnf FECParams{_cfec, paramK, paramN} =+        -- ForeignPtr has no NFData instance and I don't know how to implement+        -- one for it so we punt on it here.  We do make it strict in the+        -- record definition which at least shallowly evaluates the+        -- ForeignPtr which is ... part of the job?+        rnf paramK `seq` rnf paramN+ instance Show FECParams where-  show (FECParams _ k n) = "FEC (" ++ show k ++ ", " ++ show n ++ ")"+    show (FECParams _ k n) = "FEC (" ++ show k ++ ", " ++ show n ++ ")" -foreign import ccall unsafe "fec_new" _new :: CUInt  -- ^ k-                                           -> CUInt  -- ^ n-                                           -> IO (Ptr CFEC)+foreign import ccall unsafe "fec_init"+    _init :: IO ()+foreign import ccall unsafe "fec_new"+    _new ::+        -- | k+        CUInt ->+        -- | n+        CUInt ->+        IO (Ptr CFEC) foreign import ccall unsafe "&fec_free" _free :: FunPtr (Ptr CFEC -> IO ())-foreign import ccall unsafe "fec_encode" _encode :: Ptr CFEC-                                                 -> Ptr (Ptr Word8)  -- ^ primary blocks-                                                 -> Ptr (Ptr Word8)  -- ^ (output) secondary blocks-                                                 -> Ptr CUInt  -- ^ array of secondary block ids-                                                 -> CSize  -- ^ length of previous-                                                 -> CSize  -- ^ block length-                                                 -> IO ()-foreign import ccall unsafe "fec_decode" _decode :: Ptr CFEC-                                                 -> Ptr (Ptr Word8)  -- ^ input blocks-                                                 -> Ptr (Ptr Word8)  -- ^ output blocks-                                                 -> Ptr CUInt  -- ^ array of input indexes-                                                 -> CSize  -- ^ block length-                                                 -> IO ()+foreign import ccall unsafe "fec_encode"+    _encode ::+        Ptr CFEC ->+        -- | primary blocks+        Ptr (Ptr Word8) ->+        -- | (output) secondary blocks+        Ptr (Ptr Word8) ->+        -- | array of secondary block ids+        Ptr CUInt ->+        -- | length of previous+        CSize ->+        -- | block length+        CSize ->+        IO ()+foreign import ccall unsafe "fec_decode"+    _decode ::+        Ptr CFEC ->+        -- | input blocks+        Ptr (Ptr Word8) ->+        -- | output blocks+        Ptr (Ptr Word8) ->+        -- | array of input indexes+        Ptr CUInt ->+        -- | block length+        CSize ->+        IO ()  -- | Return true if the given @k@ and @n@ values are valid isValidConfig :: Int -> Int -> Bool isValidConfig k n-  | k >= n = False-  | k < 1 = False-  | n < 1 = False-  | n > 255 = False-  | otherwise = True+    | k > n = False+    | k < 1 = False+    | n < 1 = False+    | n > 255 = False+    | otherwise = True +{- | The underlying library signaled that it has not been properly initialized+ yet.  Use @initialize@ to initialize it.+-}+data Uninitialized = Uninitialized deriving (Ord, Eq, Show)++instance Exception Uninitialized++-- A lock to ensure at most one thread attempts to initialize the underlying+-- library at a time.  Multiple initializations are harmless but concurrent+-- initializations are disallowed.+_initializationLock :: Lock+{-# NOINLINE _initializationLock #-}+_initializationLock = unsafePerformIO newLock++-- | Initialize the library.  This must be done before other APIs can succeed.+initialize :: IO ()+initialize = withLock _initializationLock _init+ -- | Return a FEC with the given parameters.-fec :: Int  -- ^ the number of primary blocks-    -> Int  -- ^ the total number blocks, must be < 256-    -> FECParams+fec ::+    -- | the number of primary blocks+    Int ->+    -- | the total number blocks, must be < 256+    Int ->+    FECParams fec k n =-  if not (isValidConfig k n)-     then error $ "Invalid FEC parameters: " ++ show k ++ " " ++ show n-     else unsafePerformIO (do-       cfec <- _new (fromIntegral k) (fromIntegral n)-       params <- newForeignPtr _free cfec-       return $ FECParams params k n)+    if not (isValidConfig k n)+        then error $ "Invalid FEC parameters: " ++ show k ++ " " ++ show n+        else+            unsafePerformIO+                ( do+                    cfec' <- _new (fromIntegral k) (fromIntegral n)+                    -- new will return null if the library hasn't been+                    -- initialized.+                    if cfec' == nullPtr+                        then throwIO Uninitialized+                        else do+                            params <- newForeignPtr _free cfec'+                            return $ FECParams params k n+                )  -- | Create a C array of unsigned from an input array-uintCArray :: [Int] -> ((Ptr CUInt) -> IO a) -> IO a-uintCArray xs f = withArray (map fromIntegral xs) f+uintCArray :: [Int] -> (Ptr CUInt -> IO a) -> IO a+uintCArray = withArray . map fromIntegral  -- | Convert a list of ByteStrings to an array of pointers to their data-byteStringsToArray :: [B.ByteString] -> ((Ptr (Ptr Word8)) -> IO a) -> IO a+byteStringsToArray :: [B.ByteString] -> (Ptr (Ptr Word8) -> IO a) -> IO a byteStringsToArray inputs f = do-  let l = length inputs-  allocaBytes (l * sizeOf (undefined :: Ptr Word8)) (\array -> do-    let inner _ [] = f array-        inner array' (bs : bss) = BU.unsafeUseAsCString bs (\ptr -> do-          poke array' $ castPtr ptr-          inner (advancePtr array' 1) bss)-    inner array inputs)+    let l = length inputs+    allocaBytes+        (l * sizeOf (undefined :: Ptr Word8))+        ( \array -> do+            let inner _ [] = f array+                inner array' (bs : bss) =+                    BU.unsafeUseAsCString+                        bs+                        ( \ptr -> do+                            poke array' $ castPtr ptr+                            inner (advancePtr array' 1) bss+                        )+            inner array inputs+        )  -- | Return True iff all the given ByteStrings are the same length allByteStringsSameLength :: [B.ByteString] -> Bool allByteStringsSameLength [] = True-allByteStringsSameLength (bs : bss) = all ((==) (B.length bs)) $ map B.length bss+allByteStringsSameLength (bs : bss) = all ((==) (B.length bs) . B.length) bss --- | Run the given function with a pointer to an array of @n@ pointers to---   buffers of size @size@. Return these buffers as a list of ByteStrings-createByteStringArray :: Int  -- ^ the number of buffers requested-                      -> Int  -- ^ the size of each buffer-                      -> ((Ptr (Ptr Word8)) -> IO ())-                      -> IO [B.ByteString]+{- | Run the given function with a pointer to an array of @n@ pointers to+   buffers of size @size@. Return these buffers as a list of ByteStrings+-}+createByteStringArray ::+    -- | the number of buffers requested+    Int ->+    -- | the size of each buffer+    Int ->+    (Ptr (Ptr Word8) -> IO ()) ->+    IO [B.ByteString] createByteStringArray n size f = do-  allocaBytes (n * sizeOf (undefined :: Ptr Word8)) (\array -> do-    allocaBytes (n * size) (\ptr -> do-      mapM_ (\i -> poke (advancePtr array i) (advancePtr ptr (size * i))) [0..(n - 1)]-      f array-      mapM (\i -> B.packCStringLen (castPtr $ advancePtr ptr (i * size), size)) [0..(n - 1)]))+    allocaBytes+        (n * sizeOf (undefined :: Ptr Word8))+        ( \array -> do+            allocaBytes+                (n * size)+                ( \ptr -> do+                    mapM_ (\i -> poke (advancePtr array i) (advancePtr ptr (size * i))) [0 .. (n - 1)]+                    f array+                    mapM (\i -> B.packCStringLen (castPtr $ advancePtr ptr (i * size), size)) [0 .. (n - 1)]+                )+        ) --- | Generate the secondary blocks from a list of the primary blocks. The---   primary blocks must be in order and all of the same size. There must be---   @k@ primary blocks.-encode :: FECParams-       -> [B.ByteString]  -- ^ a list of @k@ input blocks-       -> [B.ByteString]  -- ^ (n - k) output blocks+{- | Generate the secondary blocks from a list of the primary blocks. The+   primary blocks must be in order and all of the same size. There must be+   @k@ primary blocks.+-}+encode ::+    FECParams ->+    -- | a list of @k@ input blocks+    [B.ByteString] ->+    -- | (n - k) output blocks+    [B.ByteString] encode (FECParams params k n) inblocks-  | length inblocks /= k = error "Wrong number of blocks to FEC encode"-  | not (allByteStringsSameLength inblocks) = error "Not all inputs to FEC encode are the same length"-  | otherwise = unsafePerformIO (do-      let sz = B.length $ head inblocks-      withForeignPtr params (\cfec -> do-        byteStringsToArray inblocks (\src -> do-          createByteStringArray (n - k) sz (\fecs -> do-            uintCArray [k..(n - 1)] (\block_nums -> do-              _encode cfec src fecs block_nums (fromIntegral (n - k)) $ fromIntegral sz)))))+    | length inblocks /= k = error "Wrong number of blocks to FEC encode"+    | not (allByteStringsSameLength inblocks) = error "Not all inputs to FEC encode are the same length"+    | otherwise =+        unsafePerformIO+            ( do+                let sz = B.length $ head inblocks+                withForeignPtr+                    params+                    ( \cfec' -> do+                        byteStringsToArray+                            inblocks+                            ( \src -> do+                                createByteStringArray+                                    (n - k)+                                    sz+                                    ( \fecs -> do+                                        uintCArray+                                            [k .. (n - 1)]+                                            ( \block_nums -> do+                                                _encode cfec' src fecs block_nums (fromIntegral (n - k)) $ fromIntegral sz+                                            )+                                    )+                            )+                    )+            )  -- | A sort function for tagged assoc lists sortTagged :: [(Int, a)] -> [(Int, a)] sortTagged = sortBy (\a b -> compare (fst a) (fst b)) --- | Reorder the given list so that elements with tag numbers < the first---   argument have an index equal to their tag number (if possible)+{- | Reorder the given list so that elements with tag numbers < the first+   argument have an index equal to their tag number (if possible)+-} reorderPrimaryBlocks :: Int -> [(Int, a)] -> [(Int, a)]-reorderPrimaryBlocks n blocks = inner (sortTagged pBlocks) sBlocks [] where-  (pBlocks, sBlocks) = partition (\(tag, _) -> tag < n) blocks-  inner [] sBlocks acc = acc ++ sBlocks-  inner pBlocks [] acc = acc ++ pBlocks-  inner pBlocks@((tag, a) : ps) sBlocks@(s : ss) acc =-    if length acc == tag-       then inner ps sBlocks (acc ++ [(tag, a)])-       else inner pBlocks ss (acc ++ [s])+reorderPrimaryBlocks n blocks = inner (sortTagged pBlocks) sBlocks []+  where+    (pBlocks, sBlocks) = partition (\(tag, _) -> tag < n) blocks+    inner [] sBlocks' acc = acc ++ sBlocks'+    inner pBlocks' [] acc = acc ++ pBlocks'+    inner pBlocks'@((tag, a) : ps) sBlocks'@(s : ss) acc =+        if length acc == tag+            then inner ps sBlocks' (acc ++ [(tag, a)])+            else inner pBlocks' ss (acc ++ [s]) --- | Recover the primary blocks from a list of @k@ blocks. Each block must be---   tagged with its number (see the module comments about block numbering)-decode :: FECParams-       -> [(Int, B.ByteString)]  -- ^ a list of @k@ blocks and their index-       -> [B.ByteString]  -- ^ a list the @k@ primary blocks+{- | Recover the primary blocks from a list of @k@ blocks. Each block must be+   tagged with its number (see the module comments about block numbering)+-}+decode ::+    FECParams ->+    -- | a list of @k@ blocks and their index+    [(Int, B.ByteString)] ->+    -- | a list the @k@ primary blocks+    [B.ByteString] decode (FECParams params k n) inblocks-  | length (nub $ map fst inblocks) /= length (inblocks) = error "Duplicate input blocks in FEC decode"-  | any (\f -> f < 0 || f >= n) $ map fst inblocks = error "Invalid block numbers in FEC decode"-  | length inblocks /= k = error "Wrong number of blocks to FEC decode"-  | not (allByteStringsSameLength $ map snd inblocks) = error "Not all inputs to FEC decode are same length"-  | otherwise = unsafePerformIO (do-      let sz = B.length $ snd $ head inblocks-          inblocks' = reorderPrimaryBlocks k inblocks-          presentBlocks = map fst inblocks'-      withForeignPtr params (\cfec -> do-        byteStringsToArray (map snd inblocks') (\src -> do-          b <- createByteStringArray (n - k) sz (\out -> do-                 uintCArray presentBlocks (\block_nums -> do-                   _decode cfec src out block_nums $ fromIntegral sz))-          let blocks = [0..(n - 1)] \\ presentBlocks-              tagged = zip blocks b-              allBlocks = sortTagged $ tagged ++ inblocks'-          return $ take k $ map snd allBlocks)))+    | length (nub $ map fst inblocks) /= length inblocks = error "Duplicate input blocks in FEC decode"+    | any ((\f -> f < 0 || f >= n) . fst) inblocks = error "Invalid block numbers in FEC decode"+    | length inblocks /= k = error "Wrong number of blocks to FEC decode"+    | not (allByteStringsSameLength $ map snd inblocks) = error "Not all inputs to FEC decode are same length"+    | otherwise =+        unsafePerformIO+            ( do+                let sz = B.length $ snd $ head inblocks+                    inblocks' = reorderPrimaryBlocks k inblocks+                    presentBlocks = map fst inblocks'+                withForeignPtr+                    params+                    ( \cfec' -> do+                        byteStringsToArray+                            (map snd inblocks')+                            ( \src -> do+                                b <-+                                    createByteStringArray+                                        (n - k)+                                        sz+                                        ( \out -> do+                                            uintCArray+                                                presentBlocks+                                                ( \block_nums -> do+                                                    _decode cfec' src out block_nums $ fromIntegral sz+                                                )+                                        )+                                let blocks = [0 .. (n - 1)] \\ presentBlocks+                                    tagged = zip blocks b+                                    allBlocks = sortTagged $ tagged ++ inblocks'+                                return $ take k $ map snd allBlocks+                            )+                    )+            ) --- | Break a ByteString into @n@ parts, equal in length to the original, such---   that all @n@ are required to reconstruct the original, but having less---   than @n@ parts reveals no information about the orginal.------   This code works in IO monad because it needs a source of random bytes,---   which it gets from /dev/urandom. If this file doesn't exist an---   exception results------   Not terribly fast - probably best to do it with short inputs (e.g. an---   encryption key)-secureDivide :: Int  -- ^ the number of parts requested-             -> B.ByteString  -- ^ the data to be split-             -> IO [B.ByteString]+{- | Break a ByteString into @n@ parts, equal in length to the original, such+   that all @n@ are required to reconstruct the original, but having less+   than @n@ parts reveals no information about the orginal.++   This code works in IO monad because it needs a source of random bytes,+   which it gets from /dev/urandom. If this file doesn't exist an+   exception results++   Not terribly fast - probably best to do it with short inputs (e.g. an+   encryption key)+-}+secureDivide ::+    -- | the number of parts requested+    Int ->+    -- | the data to be split+    B.ByteString ->+    IO [B.ByteString] secureDivide n input-  | n < 0 = error "secureDivide called with negative number of parts"-  | otherwise = withFile "/dev/urandom" ReadMode (\handle -> do-      let inner 1 bs = return [bs]-          inner n bs = do-            mask <- B.hGet handle (B.length bs)-            let masked = B.pack $ B.zipWith xor bs mask-            rest <- inner (n - 1) masked-            return (mask : rest)-      inner n input)+    | n < 0 = error "secureDivide called with negative number of parts"+    | otherwise =+        withFile+            "/dev/urandom"+            ReadMode+            ( \handle -> do+                let inner 1 bs = return [bs]+                    inner n' bs = do+                        mask <- B.hGet handle (B.length bs)+                        let masked = B.pack $ B.zipWith xor bs mask+                        rest <- inner (n' - 1) masked+                        return (mask : rest)+                inner n input+            ) --- | Reverse the operation of secureDivide. The order of the inputs doesn't---   matter, but they must all be the same length+{- | Reverse the operation of secureDivide. The order of the inputs doesn't+   matter, but they must all be the same length+-} secureCombine :: [B.ByteString] -> B.ByteString secureCombine [] = error "Passed empty list of inputs to secureCombine" secureCombine [a] = a secureCombine [a, b] = B.pack $ B.zipWith xor a b secureCombine (a : rest) = B.pack $ B.zipWith xor a $ secureCombine rest --- | A utility function which takes an arbitary input and FEC encodes it into a---   number of blocks. The order the resulting blocks doesn't matter so long---   as you have enough to present to @deFEC@.-enFEC :: Int  -- ^ the number of blocks required to reconstruct-      -> Int  -- ^ the total number of blocks-      -> B.ByteString  -- ^ the data to divide-      -> [B.ByteString]  -- ^ the resulting blocks-enFEC k n input = taggedPrimaryBlocks ++ taggedSecondaryBlocks where-  taggedPrimaryBlocks = map (uncurry B.cons) $ zip [0..] primaryBlocks-  taggedSecondaryBlocks = map (uncurry B.cons) $ zip [(fromIntegral k)..] secondaryBlocks-  remainder = B.length input `mod` k-  paddingLength = if remainder >= 1 then (k - remainder) else k-  paddingBytes = (B.replicate (paddingLength - 1) 0) `B.append` (B.singleton $ fromIntegral paddingLength)-  divide a bs-    | B.null bs = []-    | otherwise = (B.take a bs) : (divide a $ B.drop a bs)-  input' = input `B.append` paddingBytes-  blockSize = B.length input' `div` k-  primaryBlocks = divide blockSize input'-  secondaryBlocks = encode params primaryBlocks-  params = fec k n+{- | A utility function which takes an arbitary input and FEC encodes it into a+   number of blocks. The order the resulting blocks doesn't matter so long+   as you have enough to present to @deFEC@.+-}+enFEC ::+    -- | the number of blocks required to reconstruct+    Int ->+    -- | the total number of blocks+    Int ->+    -- | the data to divide+    B.ByteString ->+    -- | the resulting blocks+    [B.ByteString]+enFEC k n input = taggedPrimaryBlocks ++ taggedSecondaryBlocks+  where+    taggedPrimaryBlocks = zipWith B.cons [0 ..] primaryBlocks+    taggedSecondaryBlocks = zipWith B.cons [(fromIntegral k) ..] secondaryBlocks+    remainder = B.length input `mod` k+    paddingLength = if remainder >= 1 then k - remainder else k+    paddingBytes = B.replicate (paddingLength - 1) 0 `B.append` B.singleton (fromIntegral paddingLength)+    divide a bs+        | B.null bs = []+        | otherwise = B.take a bs : divide a (B.drop a bs)+    input' = input `B.append` paddingBytes+    blockSize = B.length input' `div` k+    primaryBlocks = divide blockSize input'+    secondaryBlocks = encode params primaryBlocks+    params = fec k n  -- | Reverses the operation of @enFEC@.-deFEC :: Int  -- ^ the number of blocks required (matches call to @enFEC@)-      -> Int  -- ^ the total number of blocks (matches call to @enFEC@)-      -> [B.ByteString]  -- ^ a list of k, or more, blocks from @enFEC@-      -> B.ByteString+deFEC ::+    -- | the number of blocks required (matches call to @enFEC@)+    Int ->+    -- | the total number of blocks (matches call to @enFEC@)+    Int ->+    -- | a list of k, or more, blocks from @enFEC@+    [B.ByteString] ->+    B.ByteString deFEC k n inputs-  | length inputs < k = error "Too few inputs to deFEC"-  | otherwise = B.take (B.length fecOutput - paddingLength) fecOutput where-      paddingLength = fromIntegral $ B.last fecOutput-      inputs' = take k inputs-      taggedInputs = map (\bs -> (fromIntegral $ B.head bs, B.tail bs)) inputs'-      fecOutput = B.concat $ decode params taggedInputs-      params = fec k n+    | length inputs < k = error "Too few inputs to deFEC"+    | otherwise = B.take (B.length fecOutput - paddingLength) fecOutput+  where+    paddingLength = fromIntegral $ B.last fecOutput+    inputs' = take k inputs+    taggedInputs = map (\bs -> (fromIntegral $ B.head bs, B.tail bs)) inputs'+    fecOutput = B.concat $ decode params taggedInputs+    params = fec k n

@@ -0,0 +1,153 @@+{-# LANGUAGE DerivingStrategies #-}++module Main where++import Test.Hspec (describe, hspec, it, parallel)++import qualified Codec.FEC as FEC+import qualified Data.ByteString as B+import qualified Data.ByteString.Lazy as BL+import Data.List (sortOn)+import Data.Word (Word16, Word8)+import System.Random (Random (randoms), mkStdGen)+import Test.QuickCheck (+    Arbitrary (arbitrary),+    Property,+    Testable (property),+    choose,+    conjoin,+    once,+    withMaxSuccess,+    (===),+ )+import Test.QuickCheck.Monadic (assert, monadicIO, run)++-- Imported for the orphan Arbitrary ByteString instance.++import Control.Monad (replicateM_)+import Test.QuickCheck.Instances.ByteString ()++-- | Valid ZFEC parameters.+data Params = Params+    { required :: Int -- aka k+    , total :: Int -- aka n+    }+    deriving (Show, Ord, Eq)++-- | A somewhat efficient generator for valid ZFEC parameters.+instance Arbitrary Params where+    arbitrary =+        choose (1, 255)+            >>= \req -> Params req <$> choose (req, 255)++randomTake :: Int -> Int -> [a] -> [a]+randomTake seed n values = map snd $ take n sortedValues+  where+    sortedValues = sortOn fst taggedValues+    taggedValues = zip rnds values+    rnds :: [Float]+    rnds = randoms gen+    gen = mkStdGen seed++{- | Any combination of the inputs blocks and the output blocks from+ @FEC.encode@, as long as there are at least @k@ of them, can be recombined+ using @FEC.decode@ to produce the original input blocks.+-}+testFEC ::+    -- | The FEC parameters to exercise.+    FEC.FECParams ->+    -- | The length of the blocks to exercise.+    Word16 ->+    -- | A random seed to use to be able to vary the choice of which blocks to+    -- try to decode.+    Int ->+    -- | True if the encoded input was reconstructed by decoding, False+    -- otherwise.+    Bool+testFEC fec len seed = FEC.decode fec someTaggedBlocks == origBlocks+  where+    -- Construct some blocks.  Each will just be the byte corresponding to the+    -- block number repeated to satisfy the requested length.+    origBlocks = B.replicate (fromIntegral len) . fromIntegral <$> [0 .. (FEC.paramK fec - 1)]++    -- Encode the data to produce the "secondary" blocks which (might) add+    -- redundancy to the original blocks.+    secondaryBlocks = FEC.encode fec origBlocks++    -- Tag each block with its block number because the decode API requires+    -- this information.+    taggedBlocks = zip [0 ..] (origBlocks ++ secondaryBlocks)++    -- Choose enough of the tagged blocks (some combination of original and+    -- secondary) to try to use for decoding.+    someTaggedBlocks = randomTake seed (FEC.paramK fec) taggedBlocks++-- | @FEC.secureDivide@ is the inverse of @FEC.secureCombine@.+prop_divide :: Word16 -> Word8 -> Word8 -> Property+prop_divide size byte divisor = monadicIO $ do+    let input = B.replicate (fromIntegral size + 1) byte+    parts <- run $ FEC.secureDivide (fromIntegral divisor) input+    assert (FEC.secureCombine parts == input)++-- | @FEC.encode@ is the inverse of @FEC.decode@.+prop_decode :: Params -> Word16 -> Int -> Property+prop_decode (Params req tot) len seed = property $ do+    testFEC fec len seed === True+  where+    fec = FEC.fec req tot++-- | @FEC.enFEC@ is the inverse of @FEC.deFEC@.+prop_deFEC :: Params -> B.ByteString -> Property+prop_deFEC (Params req tot) testdata =+    FEC.deFEC req tot minimalShares === testdata+  where+    allShares = FEC.enFEC req tot testdata+    minimalShares = take req allShares++prop_primary_copies :: Params -> BL.ByteString -> Property+prop_primary_copies (Params _ tot) primary = property $ do+    conjoin $ (BL.toStrict primary ===) <$> secondary+  where+    fec = FEC.fec 1 tot+    secondary = FEC.encode fec [BL.toStrict primary]++main :: IO ()+main = do+    -- Be sure to do the required zfec initialization first.+    FEC.initialize+    hspec . parallel $ do+        describe "encode" $ do+            -- This test originally caught a bug in multi-threaded+            -- initialization of the C library.  Since it is in the+            -- initialization codepath, it cannot catch the bug if it runs+            -- after initialization has happened.  So we put it first in the+            -- suite and hope that nothing manages to get in before this.+            --+            -- Since the bug has to do with multi-threaded use, we also make a+            -- lot of copies of this property so hspec can run them in parallel+            -- (QuickCheck will not do anything in parallel inside a single+            -- property).+            --+            -- Still, there's non-determinism and the behavior is only revealed+            -- by this property sometimes.+            replicateM_ 20 $+                it "returns copies of the primary block for all 1 of N encodings" $+                    withMaxSuccess 5 prop_primary_copies++        describe "secureCombine" $ do+            -- secureDivide is insanely slow and memory hungry for large inputs,+            -- like QuickCheck will find with it as currently defined.  Just pass+            -- some small inputs.  It's not clear it's worth fixing (or even+            -- keeping) thesefunctions.  They don't seem to be used by anything.+            -- Why are they here?+            it "is the inverse of secureDivide n" $ once $ prop_divide 1024 65 3++        describe "deFEC" $ do+            replicateM_ 10 $+                it "is the inverse of enFEC" $+                    property prop_deFEC++        describe "decode" $+            replicateM_ 10 $ do+                it "is (nearly) the inverse of encode" $ property $ prop_decode+                it "works with required=255" $ property $ prop_decode (Params 255 255)

@@ -229,11 +229,11 @@  * Return non-zero if singular.  */ static void-_invert_mat(gf* src, unsigned k) {-    gf c, *p;-    unsigned irow = 0;-    unsigned icol = 0;-    unsigned row, col, i, ix;+_invert_mat(gf* src, size_t k) {+    gf c;+    size_t irow = 0;+    size_t icol = 0;+    size_t row, col, i, ix;      unsigned* indxc = (unsigned*) malloc (k * sizeof(unsigned));     unsigned* indxr = (unsigned*) malloc (k * sizeof(unsigned));@@ -306,7 +306,8 @@          */         id_row[icol] = 1;         if (memcmp (pivot_row, id_row, k * sizeof (gf)) != 0) {-            for (p = src, ix = 0; ix < k; ix++, p += k) {+            gf *p = src;+            for (ix = 0; ix < k; ix++, p += k) {                 if (ix != icol) {                     c = p[icol];                     p[icol] = 0;@@ -320,6 +321,10 @@         if (indxr[col-1] != indxc[col-1])             for (row = 0; row < k; row++)                 SWAP (src[row * k + indxr[col-1]], src[row * k + indxc[col-1]], gf);+    free(indxc);+    free(indxr);+    free(ipiv);+    free(id_row); }  /*@@ -388,12 +393,23 @@     return; } +/* There are few (if any) ordering guarantees that apply to reads and writes+ * of this static int across threads.  This is the reason for some of the+ * tight requirements for how `fec_init` is called.  If we could use a mutex+ * or a C11 atomic here we might be able to provide more flexibility to+ * callers.  It's tricky to do that while remaining compatible with all of+ * macOS/Linux/Windows and CPython's MSVC requirements and not switching to+ * C++ (or something even more different).+ */ static int fec_initialized = 0;-static void-init_fec (void) {-    generate_gf();-    _init_mul_table();-    fec_initialized = 1;++void+fec_init (void) {+    if (fec_initialized == 0) {+        generate_gf();+        _init_mul_table();+        fec_initialized = 1;+    } }  /*@@ -412,15 +428,21 @@ }  fec_t *-fec_new(unsigned k, unsigned n) {+fec_new(unsigned short k, unsigned short n) {     unsigned row, col;     gf *p, *tmp_m;      fec_t *retval; -    if (fec_initialized == 0)-        init_fec ();+    assert(k >= 1);+    assert(n >= 1);+    assert(n <= 256);+    assert(k <= n); +    if (fec_initialized == 0) {+        return NULL;+    }+     retval = (fec_t *) malloc (sizeof (fec_t));     retval->k = k;     retval->n = n;@@ -434,7 +456,7 @@     tmp_m[0] = 1;     for (col = 1; col < k; col++)         tmp_m[col] = 0;-    for (p = tmp_m + k, row = 0; row < n - 1; row++, p += k)+    for (p = tmp_m + k, row = 0; row + 1 < n; row++, p += k)         for (col = 0; col < k; col++)             p[col] = gf_exp[modnn (row * col)]; @@ -456,9 +478,11 @@     return retval; } -/* To make sure that we stay within cache in the inner loops of fec_encode()-   and fec_decode(). */+/* To make sure that we stay within cache in the inner loops of fec_encode().  (It would+   probably help to also do this for fec_decode(). */+#ifndef STRIDE #define STRIDE 8192+#endif  void fec_encode(const fec_t* code, const gf*restrict const*restrict const src, gf*restrict const*restrict const fecs, const unsigned*restrict const block_nums, size_t num_block_nums, size_t sz) {@@ -487,7 +511,7 @@  */ void build_decode_matrix_into_space(const fec_t*restrict const code, const unsigned*const restrict index, const unsigned k, gf*restrict const matrix) {-    unsigned char i;+    unsigned short i;     gf* p;     for (i=0, p=matrix; i < k; i++, p += k) {         if (index[i] < k) {@@ -503,9 +527,22 @@ void fec_decode(const fec_t* code, const gf*restrict const*restrict const inpkts, gf*restrict const*restrict const outpkts, const unsigned*restrict const index, size_t sz) {     gf* m_dec = (gf*)alloca(code->k * code->k);++    /* char is large enough for outix - it counts the number of primary blocks+       we are decoding for return.  the most primary blocks we might have to+       decode is for k == 128, m == 256.  in this case we might be given 128+       secondary blocks and have to decode 128 primary blocks.  if k decreases+       then the number of total blocks we might have to return decreases.  if+       k increases then the number of secondary blocks that exist decreases so+       we will be passed some primary blocks and the number of primary blocks+       we have to decode decreases. */     unsigned char outix=0;-    unsigned char row=0;-    unsigned char col=0;++    /* row and col are compared directly to k, which could be 256, so make+       them large enough to represent 256.+     */+    unsigned short row=0;+    unsigned short col=0;     build_decode_matrix_into_space(code, index, code->k, m_dec);      for (row=0; row<code->k; row++) {@@ -521,13 +558,13 @@  /**  * zfec -- fast forward error correction library with Python interface- * - * Copyright (C) 2007 Allmydata, Inc.+ *+ * Copyright (C) 2007-2010 Zooko Wilcox-O'Hearn  * Author: Zooko Wilcox-O'Hearn- * + *  * This file is part of zfec.- * - * See README.txt for licensing information.+ *+ * See README.rst for licensing information.  */  /*@@ -540,7 +577,7 @@  * Robert Morelos-Zaragoza (robert@spectra.eng.hawaii.edu) and Hari  * Thirumoorthy (harit@spectra.eng.hawaii.edu), Aug 1995  *- * Modifications by Dan Rubenstein (see Modifications.txt for + * Modifications by Dan Rubenstein (see Modifications.txt for  * their description.  * Modifications (C) 1998 Dan Rubenstein (drubenst@cs.umass.edu)  *

@@ -1,5 +1,7 @@ /**  * zfec -- fast forward error correction library with Python interface+ *+ * See README.rst for documentation.  */  #include <stddef.h>@@ -8,7 +10,7 @@  typedef struct {   unsigned long magic;-  unsigned k, n;                     /* parameters of the code */+  unsigned short k, n;                     /* parameters of the code */   gf* enc_matrix; } fec_t; @@ -18,11 +20,23 @@ #define restrict #endif +/** Initialize the fec library.+ *+ * Call this:+ *+ *  - at least once+ *  - from at most one thread at a time+ *  - before calling any other APIs from the library+ *  - before creating any other threads that will use APIs from the library+ *+ */+void fec_init(void);+ /**  * param k the number of blocks required to reconstruct  * param m the total number of blocks created  */-fec_t* fec_new(unsigned k, unsigned m);+fec_t* fec_new(unsigned short k, unsigned short m); void fec_free(fec_t* p);  /**@@ -62,7 +76,7 @@  *   * This file is part of zfec.  * - * See README.txt for licensing information.+ * See README.rst for licensing information.  */  /*