diff options
Diffstat (limited to 'kopete/protocols/msn/webcam/libmimic')
18 files changed, 4406 insertions, 0 deletions
diff --git a/kopete/protocols/msn/webcam/libmimic/AUTHORS b/kopete/protocols/msn/webcam/libmimic/AUTHORS new file mode 100644 index 00000000..8dd0671d --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/AUTHORS @@ -0,0 +1,2 @@ +Ole André Vadla RavnÃ¥s <oleavr@gmail.com> + diff --git a/kopete/protocols/msn/webcam/libmimic/COPYING b/kopete/protocols/msn/webcam/libmimic/COPYING new file mode 100644 index 00000000..b1e3f5a2 --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/COPYING @@ -0,0 +1,504 @@ + GNU LESSER GENERAL PUBLIC LICENSE + Version 2.1, February 1999 + + Copyright (C) 1991, 1999 Free Software Foundation, Inc. + 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + +[This is the first released version of the Lesser GPL. It also counts + as the successor of the GNU Library Public License, version 2, hence + the version number 2.1.] + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +Licenses are intended to guarantee your freedom to share and change +free software--to make sure the software is free for all its users. + + This license, the Lesser General Public License, applies to some +specially designated software packages--typically libraries--of the +Free Software Foundation and other authors who decide to use it. You +can use it too, but we suggest you first think carefully about whether +this license or the ordinary General Public License is the better +strategy to use in any particular case, based on the explanations below. + + When we speak of free software, we are referring to freedom of use, +not price. Our General Public Licenses are designed to make sure that +you have the freedom to distribute copies of free software (and charge +for this service if you wish); that you receive source code or can get +it if you want it; that you can change the software and use pieces of +it in new free programs; and that you are informed that you can do +these things. + + To protect your rights, we need to make restrictions that forbid +distributors to deny you these rights or to ask you to surrender these +rights. These restrictions translate to certain responsibilities for +you if you distribute copies of the library or if you modify it. + + For example, if you distribute copies of the library, whether gratis +or for a fee, you must give the recipients all the rights that we gave +you. You must make sure that they, too, receive or can get the source +code. If you link other code with the library, you must provide +complete object files to the recipients, so that they can relink them +with the library after making changes to the library and recompiling +it. And you must show them these terms so they know their rights. + + We protect your rights with a two-step method: (1) we copyright the +library, and (2) we offer you this license, which gives you legal +permission to copy, distribute and/or modify the library. + + To protect each distributor, we want to make it very clear that +there is no warranty for the free library. Also, if the library is +modified by someone else and passed on, the recipients should know +that what they have is not the original version, so that the original +author's reputation will not be affected by problems that might be +introduced by others. + + Finally, software patents pose a constant threat to the existence of +any free program. We wish to make sure that a company cannot +effectively restrict the users of a free program by obtaining a +restrictive license from a patent holder. Therefore, we insist that +any patent license obtained for a version of the library must be +consistent with the full freedom of use specified in this license. + + Most GNU software, including some libraries, is covered by the +ordinary GNU General Public License. This license, the GNU Lesser +General Public License, applies to certain designated libraries, and +is quite different from the ordinary General Public License. We use +this license for certain libraries in order to permit linking those +libraries into non-free programs. + + When a program is linked with a library, whether statically or using +a shared library, the combination of the two is legally speaking a +combined work, a derivative of the original library. The ordinary +General Public License therefore permits such linking only if the +entire combination fits its criteria of freedom. The Lesser General +Public License permits more lax criteria for linking other code with +the library. + + We call this license the "Lesser" General Public License because it +does Less to protect the user's freedom than the ordinary General +Public License. It also provides other free software developers Less +of an advantage over competing non-free programs. These disadvantages +are the reason we use the ordinary General Public License for many +libraries. However, the Lesser license provides advantages in certain +special circumstances. + + For example, on rare occasions, there may be a special need to +encourage the widest possible use of a certain library, so that it becomes +a de-facto standard. To achieve this, non-free programs must be +allowed to use the library. A more frequent case is that a free +library does the same job as widely used non-free libraries. In this +case, there is little to gain by limiting the free library to free +software only, so we use the Lesser General Public License. + + In other cases, permission to use a particular library in non-free +programs enables a greater number of people to use a large body of +free software. For example, permission to use the GNU C Library in +non-free programs enables many more people to use the whole GNU +operating system, as well as its variant, the GNU/Linux operating +system. + + Although the Lesser General Public License is Less protective of the +users' freedom, it does ensure that the user of a program that is +linked with the Library has the freedom and the wherewithal to run +that program using a modified version of the Library. + + The precise terms and conditions for copying, distribution and +modification follow. Pay close attention to the difference between a +"work based on the library" and a "work that uses the library". The +former contains code derived from the library, whereas the latter must +be combined with the library in order to run. + + GNU LESSER GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License Agreement applies to any software library or other +program which contains a notice placed by the copyright holder or +other authorized party saying it may be distributed under the terms of +this Lesser General Public License (also called "this License"). +Each licensee is addressed as "you". + + A "library" means a collection of software functions and/or data +prepared so as to be conveniently linked with application programs +(which use some of those functions and data) to form executables. + + The "Library", below, refers to any such software library or work +which has been distributed under these terms. A "work based on the +Library" means either the Library or any derivative work under +copyright law: that is to say, a work containing the Library or a +portion of it, either verbatim or with modifications and/or translated +straightforwardly into another language. (Hereinafter, translation is +included without limitation in the term "modification".) + + "Source code" for a work means the preferred form of the work for +making modifications to it. For a library, complete source code means +all the source code for all modules it contains, plus any associated +interface definition files, plus the scripts used to control compilation +and installation of the library. + + Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running a program using the Library is not restricted, and output from +such a program is covered only if its contents constitute a work based +on the Library (independent of the use of the Library in a tool for +writing it). Whether that is true depends on what the Library does +and what the program that uses the Library does. + + 1. You may copy and distribute verbatim copies of the Library's +complete source code as you receive it, in any medium, provided that +you conspicuously and appropriately publish on each copy an +appropriate copyright notice and disclaimer of warranty; keep intact +all the notices that refer to this License and to the absence of any +warranty; and distribute a copy of this License along with the +Library. + + You may charge a fee for the physical act of transferring a copy, +and you may at your option offer warranty protection in exchange for a +fee. + + 2. You may modify your copy or copies of the Library or any portion +of it, thus forming a work based on the Library, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) The modified work must itself be a software library. + + b) You must cause the files modified to carry prominent notices + stating that you changed the files and the date of any change. + + c) You must cause the whole of the work to be licensed at no + charge to all third parties under the terms of this License. + + d) If a facility in the modified Library refers to a function or a + table of data to be supplied by an application program that uses + the facility, other than as an argument passed when the facility + is invoked, then you must make a good faith effort to ensure that, + in the event an application does not supply such function or + table, the facility still operates, and performs whatever part of + its purpose remains meaningful. + + (For example, a function in a library to compute square roots has + a purpose that is entirely well-defined independent of the + application. Therefore, Subsection 2d requires that any + application-supplied function or table used by this function must + be optional: if the application does not supply it, the square + root function must still compute square roots.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Library, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Library, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote +it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Library. + +In addition, mere aggregation of another work not based on the Library +with the Library (or with a work based on the Library) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may opt to apply the terms of the ordinary GNU General Public +License instead of this License to a given copy of the Library. To do +this, you must alter all the notices that refer to this License, so +that they refer to the ordinary GNU General Public License, version 2, +instead of to this License. (If a newer version than version 2 of the +ordinary GNU General Public License has appeared, then you can specify +that version instead if you wish.) Do not make any other change in +these notices. + + Once this change is made in a given copy, it is irreversible for +that copy, so the ordinary GNU General Public License applies to all +subsequent copies and derivative works made from that copy. + + This option is useful when you wish to copy part of the code of +the Library into a program that is not a library. + + 4. You may copy and distribute the Library (or a portion or +derivative of it, under Section 2) in object code or executable form +under the terms of Sections 1 and 2 above provided that you accompany +it with the complete corresponding machine-readable source code, which +must be distributed under the terms of Sections 1 and 2 above on a +medium customarily used for software interchange. + + If distribution of object code is made by offering access to copy +from a designated place, then offering equivalent access to copy the +source code from the same place satisfies the requirement to +distribute the source code, even though third parties are not +compelled to copy the source along with the object code. + + 5. A program that contains no derivative of any portion of the +Library, but is designed to work with the Library by being compiled or +linked with it, is called a "work that uses the Library". Such a +work, in isolation, is not a derivative work of the Library, and +therefore falls outside the scope of this License. + + However, linking a "work that uses the Library" with the Library +creates an executable that is a derivative of the Library (because it +contains portions of the Library), rather than a "work that uses the +library". The executable is therefore covered by this License. +Section 6 states terms for distribution of such executables. + + When a "work that uses the Library" uses material from a header file +that is part of the Library, the object code for the work may be a +derivative work of the Library even though the source code is not. +Whether this is true is especially significant if the work can be +linked without the Library, or if the work is itself a library. The +threshold for this to be true is not precisely defined by law. + + If such an object file uses only numerical parameters, data +structure layouts and accessors, and small macros and small inline +functions (ten lines or less in length), then the use of the object +file is unrestricted, regardless of whether it is legally a derivative +work. (Executables containing this object code plus portions of the +Library will still fall under Section 6.) + + Otherwise, if the work is a derivative of the Library, you may +distribute the object code for the work under the terms of Section 6. +Any executables containing that work also fall under Section 6, +whether or not they are linked directly with the Library itself. + + 6. As an exception to the Sections above, you may also combine or +link a "work that uses the Library" with the Library to produce a +work containing portions of the Library, and distribute that work +under terms of your choice, provided that the terms permit +modification of the work for the customer's own use and reverse +engineering for debugging such modifications. + + You must give prominent notice with each copy of the work that the +Library is used in it and that the Library and its use are covered by +this License. You must supply a copy of this License. If the work +during execution displays copyright notices, you must include the +copyright notice for the Library among them, as well as a reference +directing the user to the copy of this License. Also, you must do one +of these things: + + a) Accompany the work with the complete corresponding + machine-readable source code for the Library including whatever + changes were used in the work (which must be distributed under + Sections 1 and 2 above); and, if the work is an executable linked + with the Library, with the complete machine-readable "work that + uses the Library", as object code and/or source code, so that the + user can modify the Library and then relink to produce a modified + executable containing the modified Library. (It is understood + that the user who changes the contents of definitions files in the + Library will not necessarily be able to recompile the application + to use the modified definitions.) + + b) Use a suitable shared library mechanism for linking with the + Library. A suitable mechanism is one that (1) uses at run time a + copy of the library already present on the user's computer system, + rather than copying library functions into the executable, and (2) + will operate properly with a modified version of the library, if + the user installs one, as long as the modified version is + interface-compatible with the version that the work was made with. + + c) Accompany the work with a written offer, valid for at + least three years, to give the same user the materials + specified in Subsection 6a, above, for a charge no more + than the cost of performing this distribution. + + d) If distribution of the work is made by offering access to copy + from a designated place, offer equivalent access to copy the above + specified materials from the same place. + + e) Verify that the user has already received a copy of these + materials or that you have already sent this user a copy. + + For an executable, the required form of the "work that uses the +Library" must include any data and utility programs needed for +reproducing the executable from it. However, as a special exception, +the materials to be distributed need not include anything that is +normally distributed (in either source or binary form) with the major +components (compiler, kernel, and so on) of the operating system on +which the executable runs, unless that component itself accompanies +the executable. + + It may happen that this requirement contradicts the license +restrictions of other proprietary libraries that do not normally +accompany the operating system. Such a contradiction means you cannot +use both them and the Library together in an executable that you +distribute. + + 7. You may place library facilities that are a work based on the +Library side-by-side in a single library together with other library +facilities not covered by this License, and distribute such a combined +library, provided that the separate distribution of the work based on +the Library and of the other library facilities is otherwise +permitted, and provided that you do these two things: + + a) Accompany the combined library with a copy of the same work + based on the Library, uncombined with any other library + facilities. This must be distributed under the terms of the + Sections above. + + b) Give prominent notice with the combined library of the fact + that part of it is a work based on the Library, and explaining + where to find the accompanying uncombined form of the same work. + + 8. You may not copy, modify, sublicense, link with, or distribute +the Library except as expressly provided under this License. Any +attempt otherwise to copy, modify, sublicense, link with, or +distribute the Library is void, and will automatically terminate your +rights under this License. However, parties who have received copies, +or rights, from you under this License will not have their licenses +terminated so long as such parties remain in full compliance. + + 9. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Library or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Library (or any work based on the +Library), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Library or works based on it. + + 10. Each time you redistribute the Library (or any work based on the +Library), the recipient automatically receives a license from the +original licensor to copy, distribute, link with or modify the Library +subject to these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties with +this License. + + 11. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Library at all. For example, if a patent +license would not permit royalty-free redistribution of the Library by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Library. + +If any portion of this section is held invalid or unenforceable under any +particular circumstance, the balance of the section is intended to apply, +and the section as a whole is intended to apply in other circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 12. If the distribution and/or use of the Library is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Library under this License may add +an explicit geographical distribution limitation excluding those countries, +so that distribution is permitted only in or among countries not thus +excluded. In such case, this License incorporates the limitation as if +written in the body of this License. + + 13. The Free Software Foundation may publish revised and/or new +versions of the Lesser General Public License from time to time. +Such new versions will be similar in spirit to the present version, +but may differ in detail to address new problems or concerns. + +Each version is given a distinguishing version number. If the Library +specifies a version number of this License which applies to it and +"any later version", you have the option of following the terms and +conditions either of that version or of any later version published by +the Free Software Foundation. If the Library does not specify a +license version number, you may choose any version ever published by +the Free Software Foundation. + + 14. If you wish to incorporate parts of the Library into other free +programs whose distribution conditions are incompatible with these, +write to the author to ask for permission. For software which is +copyrighted by the Free Software Foundation, write to the Free +Software Foundation; we sometimes make exceptions for this. Our +decision will be guided by the two goals of preserving the free status +of all derivatives of our free software and of promoting the sharing +and reuse of software generally. + + NO WARRANTY + + 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO +WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. +EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR +OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY +KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE +LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME +THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN +WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY +AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU +FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR +CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE +LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING +RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A +FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF +SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH +DAMAGES. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Libraries + + If you develop a new library, and you want it to be of the greatest +possible use to the public, we recommend making it free software that +everyone can redistribute and change. You can do so by permitting +redistribution under these terms (or, alternatively, under the terms of the +ordinary General Public License). + + To apply these terms, attach the following notices to the library. It is +safest to attach them to the start of each source file to most effectively +convey the exclusion of warranty; and each file should have at least the +"copyright" line and a pointer to where the full notice is found. + + <one line to give the library's name and a brief idea of what it does.> + Copyright (C) <year> <name of author> + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + +Also add information on how to contact you by electronic and paper mail. + +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a "copyright disclaimer" for the library, if +necessary. Here is a sample; alter the names: + + Yoyodyne, Inc., hereby disclaims all copyright interest in the + library `Frob' (a library for tweaking knobs) written by James Random Hacker. + + <signature of Ty Coon>, 1 April 1990 + Ty Coon, President of Vice + +That's all there is to it! + + diff --git a/kopete/protocols/msn/webcam/libmimic/Makefile.am b/kopete/protocols/msn/webcam/libmimic/Makefile.am new file mode 100644 index 00000000..1a2c99d3 --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/Makefile.am @@ -0,0 +1,24 @@ +# INCLUDES = @GLIB_CFLAGS@ +AM_CPPFLAGS = $(all_includes) $(GLIB_CFLAGS) + +# libmimicincludedir = $(includedir) +# libmimicinclude_HEADERS = mimic.h + +noinst_LTLIBRARIES = libmimic.la +libmimic_la_SOURCES = \ + mimic.c \ + encode.c \ + decode.c \ + bitstring.c \ + vlc_common.c \ + vlc_encode.c \ + vlc_decode.c \ + fdct_quant.c \ + idct_dequant.c \ + colorspace.c \ + deblock.c \ + mimic-private.h +# libmimic_la_LDFLAGS = \ +# -version-info $(MIMIC_CURRENT):$(MIMIC_REVISION):$(MIMIC_AGE) \ +# -export-symbols-regex "^[^_].*" + diff --git a/kopete/protocols/msn/webcam/libmimic/README b/kopete/protocols/msn/webcam/libmimic/README new file mode 100644 index 00000000..c60336ec --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/README @@ -0,0 +1,40 @@ +ABOUT +----- + +libmimic is an open source video encoding/decoding library for Mimic V2.x- +encoded content (fourCC: ML20), which is the encoding used by MSN Messenger +for webcam conversations. + +It was written because there was no third-party MSN-client that supported +this feature due to this proprietary/unknown codec involved. I didn't like +this lack of interoperability, so I decided to do something about it. After +studying the official MSN-client a little closer, it became clear that the +codec involved was statically linked into the executable, so there was no +easy way to use the codec code through Wine. So for fun, and challenge, I +reverse-engineered the original implementation by studying the massive +amount of assembly code involved, and after a lot of hard work I ended +up with this implementation in C. + +It should be noted that reverse-engineering for interoperability is 100% +legal here in Norway (and in most European countries). + + +THANKS +------ + +Special thanks to Rob Taylor and the rest of the Farsight-team for all +the feedback and inspiration during development, you guys rock! :-) + + +BOTTOM LINE +----------- + +If you like my work and decide to use it in your project, please feel free +to credit me. I put a lot of time and hard work into this, so I hope others +will find it useful. + +Well, enough chit chat, enjoy! :-) + +Ole André Vadla RavnÃ¥s +oleavr at gmail dot com + diff --git a/kopete/protocols/msn/webcam/libmimic/bitstring.c b/kopete/protocols/msn/webcam/libmimic/bitstring.c new file mode 100644 index 00000000..2aef7284 --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/bitstring.c @@ -0,0 +1,88 @@ +/* Copyright (C) 2005 Ole André Vadla RavnÃ¥s <oleavr@gmail.com> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "mimic-private.h" + +/* + * _read_bits + * + * Internal helper-function used to read num_bits + * from stream. + */ +guint32 _read_bits(MimCtx *ctx, gint num_bits) +{ + guint32 bits; + + if (ctx->cur_chunk_len >= 16) { + guchar *input_buf = (guchar *) ctx->data_buffer + ctx->data_index; + + if (!ctx->read_odd) { + ctx->read_odd = TRUE; + + ctx->cur_chunk = (input_buf[3] << 24) | + (input_buf[2] << 16) | + (input_buf[1] << 8) | + input_buf[0]; + + } else { + ctx->read_odd = FALSE; + + ctx->cur_chunk = (input_buf[1] << 24) | + (input_buf[0] << 16) | + (input_buf[7] << 8) | + input_buf[6]; + + ctx->data_index += 4; + } + + ctx->cur_chunk_len -= 16; + } + + bits = (ctx->cur_chunk << ctx->cur_chunk_len) >> (32 - num_bits); + ctx->cur_chunk_len += num_bits; + + return bits; +} + +/* + * _write_bits + * + * Internal helper-function used to write "length" + * bits of "bits" to stream. + */ +void _write_bits(MimCtx *ctx, guint32 bits, gint length) +{ + /* Left-align the bit string within its 32-bit container. */ + bits <<= (32 - length); + + /* Append the bit string (one or more of the trailing bits might not fit, but that's ok). */ + ctx->cur_chunk |= bits >> ctx->cur_chunk_len; + ctx->cur_chunk_len += length; + + /* Is it full? */ + if (ctx->cur_chunk_len >= 32) { + + /* Add the full 32-bit chunk to the stream and update counter. */ + ctx->chunk_ptr[0] = GUINT32_TO_LE(ctx->cur_chunk); + ctx->chunk_ptr++; + ctx->cur_chunk_len -= 32; + + /* Add any trailing bits that didn't fit. */ + ctx->cur_chunk = bits << (length - ctx->cur_chunk_len); + } +} + diff --git a/kopete/protocols/msn/webcam/libmimic/colorspace.c b/kopete/protocols/msn/webcam/libmimic/colorspace.c new file mode 100644 index 00000000..620992c6 --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/colorspace.c @@ -0,0 +1,161 @@ +/* Copyright (C) 2005 Ole André Vadla RavnÃ¥s <oleavr@gmail.com> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "mimic-private.h" + +#define RED_INDEX_1 0 +#define GREEN_INDEX_1 1 +#define BLUE_INDEX_1 2 + +#define RED_INDEX_2 3 +#define GREEN_INDEX_2 4 +#define BLUE_INDEX_2 5 + +/* + * _rgb_to_yuv + * + * Internal helper-function used to convert an image + * from RGB 24-bpp packed-pixel to YUV420 planar. + */ +void _rgb_to_yuv(const guchar *input_rgb, + guchar *output_y, + guchar *output_cb, + guchar *output_cr, + gint width, + gint height) +{ + gint y, x; + + for (y = 0; y < height; y += 2) { + + const guchar *src1, *src2; + guchar *dst1, *dst2, *dst3, *dst4; + gint num_cols; + + src1 = input_rgb + ((height - 1 - y) * width * 3); + src2 = input_rgb + ((height - 2 - y) * width * 3); + + dst1 = output_y + (y * width); + dst2 = output_y + ((y + 1) * width); + dst3 = output_cb + ((y / 2) * (width / 2)); + dst4 = output_cr + ((y / 2) * (width / 2)); + + num_cols = width / 2; + + for (x = 0; x < num_cols; x++) { + + gint expr1, expr2, expr3, expr4, expr5, v; + + expr1 = (src1[BLUE_INDEX_1] * 19595) + (src1[GREEN_INDEX_1] * 38470) + (src1[RED_INDEX_1] * 7471); + expr2 = (src1[BLUE_INDEX_2] * 19595) + (src1[GREEN_INDEX_2] * 38470) + (src1[RED_INDEX_2] * 7471); + expr3 = (src2[BLUE_INDEX_1] * 19595) + (src2[GREEN_INDEX_1] * 38470) + (src2[RED_INDEX_1] * 7471); + expr4 = (src2[BLUE_INDEX_2] * 19595) + (src2[GREEN_INDEX_2] * 38470) + (src2[RED_INDEX_2] * 7471); + + expr5 = expr1 + expr2 + expr3 + expr4; + + dst1[0] = expr1 >> 16; + dst1[1] = expr2 >> 16; + dst2[0] = expr3 >> 16; + dst2[1] = expr4 >> 16; + + v = (((src1[BLUE_INDEX_1] + src1[BLUE_INDEX_2] + src2[BLUE_INDEX_1] + src2[BLUE_INDEX_2]) << 16) - expr5 + 131071) >> 16; + dst3[0] = _clamp_value(((v * 57475) >> 18) + 128); + + v = (((src1[RED_INDEX_1] + src1[RED_INDEX_2] + src2[RED_INDEX_1] + src2[RED_INDEX_2]) << 16) - expr5 + 131071) >> 16; + dst4[0] = ((v * 32244) >> 18) + 128; + + src1 += 6; + src2 += 6; + + dst1 += 2; + dst2 += 2; + dst3++; + dst4++; + + } + + } + +} + +/* + * _yuv_to_rgb + * + * Internal helper-function used to convert an image + * from YUV420 planar to RGB 24-bpp packed-pixel. + */ +void _yuv_to_rgb(const guchar *input_y, + const guchar *input_cb, + const guchar *input_cr, + guchar *output_rgb, + guint width, + guint height) +{ + const guchar *src_y, *src_cb, *src_cr; + guchar *dst_rgb; + guint i, j, rgb_stride; + + src_y = input_y; + src_cb = input_cb; + src_cr = input_cr; + + rgb_stride = width * 3; + dst_rgb = output_rgb + (rgb_stride * (height - 1)); + + for (i = 0; i < height; i++) { + const guchar *p_y, *p_cb, *p_cr; + guchar *p_rgb; + + p_y = src_y; + p_cb = src_cb; + p_cr = src_cr; + + p_rgb = dst_rgb; + + for (j = 0; j < width; j++) { + gint v; + + v = ((p_y[0] * 65536) + ((p_cr[0] - 128) * 133169)) / 65536; + p_rgb[0] = _clamp_value(v); + + v = ((p_y[0] * 65536) - ((p_cr[0] - 128) * 25821) - ((p_cb[0] - 128) * 38076)) / 65536; + p_rgb[1] = _clamp_value(v); + + v = ((p_y[0] * 65536) + ((p_cb[0] - 128) * 74711)) / 65536; + p_rgb[2] = _clamp_value(v); + + p_y++; + if ((j + 1) % 2 == 0) { + p_cb++; + p_cr++; + } + + p_rgb += 3; + } + + src_y += width; + if ((i + 1) % 2 == 0) { + src_cb += (width + 1) / 2; + src_cr += (width + 1) / 2; + } + + dst_rgb -= rgb_stride; + + } + +} + diff --git a/kopete/protocols/msn/webcam/libmimic/deblock.c b/kopete/protocols/msn/webcam/libmimic/deblock.c new file mode 100644 index 00000000..cfd6ff6d --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/deblock.c @@ -0,0 +1,450 @@ +/* Copyright (C) 2005 Ole André Vadla Ravnås <oleavr@gmail.com> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <stdlib.h> +#include <string.h> +#include "mimic-private.h" + +static void deblock_horizontal(guchar *blocks, guint stride, guint row_count); +static void deblock_vertical(guchar *blocks, guint stride, guint row_count); + +static gboolean deblock_h_consider_entire(guchar *blocks, guint stride); +static void deblock_h_do_entire(guchar *blocks, guint stride); +static void deblock_h_do_boundaries(guchar *blocks, guint stride); + +static gboolean deblock_v_consider_entire(guchar *blocks, guint stride); +static void deblock_v_do_entire(guchar *blocks, guint stride); +static void deblock_v_do_boundaries(guchar *blocks, guint stride); + +/* + * _deblock + * + * Internal helper-function used for de-blocking. + */ +void _deblock(guchar *blocks, guint stride, guint row_count) +{ + deblock_horizontal(blocks, stride, row_count); + deblock_vertical(blocks, stride, row_count); +} + +static void deblock_horizontal(guchar *blocks, guint stride, guint row_count) +{ + guchar *p1; + gint i, j, n1, n2; + + if (stride <= 8 || row_count == 0) + return; + + p1 = blocks + 4; + n1 = ((row_count - 1) >> 2) + 1; + n2 = ((stride - 9) >> 3) + 1; + + for (i = 0; i < n1; i++) { + guchar *p; + + p = p1; + + for (j = 0; j < n2; j++) { + + if (deblock_h_consider_entire(p - 1, stride) == TRUE) { + + gint v1, v2, v; + + v1 = p[0]; + v2 = p[7]; + + v = v1 - v2; + if (v <= 0) + v = v2 - v1; + + if (v < 20) + deblock_h_do_entire(p - 1, stride); + + } else { + deblock_h_do_boundaries(p - 1, stride); + } + + p += 8; + } + + p1 += stride * 4; + } +} + +static void deblock_vertical(guchar *blocks, guint stride, guint row_count) +{ + gint i, j, k, n1, n2; + guchar *p1, *p2; + + if (stride == 0 || row_count <= 8) + return; + + p1 = blocks + (stride * 3); + p2 = blocks + (stride * 4); + + n1 = ((row_count - 9) >> 3) + 1; + n2 = ((stride - 1) >> 3) + 1; + + for (i = 0; i < n1; i++) { + guchar *p3, *p4; + + p3 = p1; + p4 = p2; + + for (j = 0; j < n2; j++) { + + if (deblock_v_consider_entire(p3, stride) == TRUE) { + guchar *p5; + gboolean do_entire; + + p5 = p3 + (stride * 8); + do_entire = TRUE; + + for (k = 0; k < 8; k++) { + gint v1, v2, v; + + v1 = p4[k]; + v2 = p5[k]; + + v = v1 - v2; + if (v <= 0) + v = v2 - v1; + + if (v > 20) { + do_entire = FALSE; + break; + } + } + + if (do_entire) + deblock_v_do_entire(p3, stride); + } else { + deblock_v_do_boundaries(p3, stride); + } + + p3 += 8; + p4 += 8; + } + + p1 += stride * 8; + p2 += stride * 8; + } +} + +static gboolean deblock_h_consider_entire(guchar *blocks, guint stride) +{ + guchar *p; + gint i, j, count; + + count = 0; + p = blocks; + + for (i = 0; i < 4; i++) { + + for (j = 1; j <= 7; j++) { + gint v1, v2, v; + + v1 = p[j]; + v2 = p[j+1]; + + v = v1 - v2; + if (v <= 0) + v = v2 - v1; + + if (v <= 1) + count--; + } + + p += stride; + } + + return (count <= -20); +} + +static void deblock_h_do_entire(guchar *blocks, guint stride) +{ + guchar buf[8], *p; + gint i; + + p = blocks; + + for (i = 0; i < 4; i++) { + gint v, low, high; + + v = p[0] - p[1]; + if (v <= 0) + v = p[1] - p[0]; + + if (v < 10) + low = p[0]; + else + low = p[1]; + + v = p[8] - p[9]; + if (v <= 0) + v = p[9] - p[8]; + + if (v >= 10) + high = p[8]; + else + high = p[9]; + + v = (low * 3) + p[1] + p[2] + p[3] + p[4] + 4; + buf[0] = (((p[1] + v) << 1) - p[4] + p[5]) >> 4; + + v += p[5] - low; + buf[1] = (((p[2] + v) << 1) - p[5] + p[6]) >> 4; + + v += p[6] - low; + buf[2] = (((p[3] + v) << 1) - p[6] + p[7]) >> 4; + + v += p[7] - low; + buf[3] = (((p[4] + v) << 1) - p[1] - p[7] + p[8] + low) >> 4; + + v += p[8] - p[1]; + buf[4] = (((p[5] + v) << 1) + p[1] - p[2] - p[8] + high) >> 4; + + v += high - p[2]; + buf[5] = (((p[6] + v) << 1) + p[2] - p[3]) >> 4; + + v += high - p[3]; + buf[6] = (((p[7] + v) << 1) + p[3] - p[4]) >> 4; + + v += high; + buf[7] = (((p[8] + v) << 1) - p[4] - p[5]) >> 4; + + memcpy(p + 1, buf, 8); + + p += stride; + } +} + +static void deblock_h_do_boundaries(guchar *blocks, guint stride) +{ + guchar *p; + gint i; + + p = blocks; + + for (i = 0; i < 4; i++) { + gint v, v1, v2, v3; + + v = p[4] - p[5]; + + if ((v / 2) != 0) { + + v1 = ((p[3] - p[6]) * 2) - (v * 5); + + if (abs(v1) < 80) { + + v2 = ((p[3] - p[2]) * 5) + ((p[1] - p[4]) * 2); + v3 = (p[5] * 2) + (p[7] * 5) - (p[8] * 7); + + v = abs(v1) - MIN(abs(v2), abs(v3)); + + if (v > 0) { + + v = ((v * 5) + 32) >> 6; + if (v > 0) { + + v2 = (p[4] - p[5]) / 2; + v3 = (((v1 < 0) * 2) - 1) * v; + + if (v2 > 0) + v = MIN(v2, ((v3 < 0) - 1) & v3); + else + v = MAX(v2, ((v3 > 0) - 1) & v3); + + p[4] -= v; + p[5] += v; + } + } + } + } + + p += stride; + } +} + +static gboolean deblock_v_consider_entire(guchar *blocks, guint stride) +{ + gint count, i, j; + guchar *p1, *p2; + + count = 0; + + p1 = blocks + stride; + p2 = blocks + (stride * 2); + + for (i = 0; i < 7; i++) { + + for (j = 0; j < 8; j++) { + gint v1, v2, v; + + v1 = p1[j]; + v2 = p2[j]; + + v = v1 - v2; + if (v <= 0) + v = v2 - v1; + + if (v <= 1) + count++; + } + + p1 += stride; + p2 += stride; + } + + return (count > 40); +} + +static void deblock_v_do_entire(guchar *blocks, guint stride) +{ + gint offset0, offset1, offset2, offset3; + gint offset4, offset5, offset6, offset7; + gint offset8, i; + guchar *p, buf[8]; + + offset0 = stride - (stride * 6); + offset1 = (stride * 2) - (stride * 6); + offset2 = (stride * 3) - (stride * 6); + offset3 = (stride * 4) - (stride * 6); + offset4 = (stride * 5) - (stride * 6); + offset5 = 0; + offset6 = (stride * 7) - (stride * 6); + offset7 = (stride * 8) - (stride * 6); + offset8 = (stride * 9) - (stride * 6); + + p = blocks + (stride * 6); + + for (i = 0; i < 8; i++) { + gint v, low, high; + + v = blocks[i] - p[offset0]; + if (v <= 0) + v = p[offset0] - blocks[i]; + + if (v < 10) + low = blocks[i]; + else + low = p[offset0]; + + v = p[offset7] - p[offset8]; + if (v <= 0) + v = p[offset8] - p[offset7]; + + if (v < 10) + high = p[offset8]; + else + high = p[offset7]; + + v = p[offset0] + (low * 3) + p[offset1] + p[offset2] + p[offset3] + 4; + + buf[0] = (((p[offset0] + v) << 1) - p[offset3] + p[offset4]) >> 4; + + v += p[offset4] - low; + + buf[1] = (((p[offset1] + v) << 1) - p[offset4] + p[0]) >> 4; + + v += p[0] - low; + + buf[2] = (((p[offset2] + v) << 1) - p[0] + p[offset6]) >> 4; + + v += p[offset6] - low; + + buf[3] = (((p[offset3] + v) << 1) - p[offset0] - p[offset6] + p[offset7] + low) >> 4; + + v += p[offset7] - p[offset0]; + + buf[4] = (((p[offset4] + v) << 1) - p[offset7] - p[offset1] + p[offset0] + high) >> 4; + + v += high - p[offset1]; + + buf[5] = (((p[0] + v) << 1) - p[offset2] + p[offset1]) >> 4; + + v += high - p[offset2]; + + buf[6] = (((p[offset6] + v) << 1) - p[offset3] + p[offset2]) >> 4; + + v += high; + + buf[7] = (((p[offset7] + v) << 1) - p[offset4] - p[offset3]) >> 4; + + p[offset0] = buf[0]; + p[offset1] = buf[1]; + p[offset2] = buf[2]; + p[offset3] = buf[3]; + p[offset4] = buf[4]; + p[offset5] = buf[5]; + p[offset6] = buf[6]; + p[offset7] = buf[7]; + + p++; + } +} + +static void deblock_v_do_boundaries(guchar *blocks, guint stride) +{ + guchar *p; + gint offset0, offset1, offset2, offset3; + gint offset4, offset5, offset6, offset7; + gint i; + + p = blocks + (stride * 3); + + offset0 = stride - (stride * 3); + offset1 = (stride * 2) - (stride * 3); + offset2 = 0; + offset3 = (stride * 4) - (stride * 3); + offset4 = (stride * 5) - (stride * 3); + offset5 = (stride * 6) - (stride * 3); + offset6 = (stride * 7) - (stride * 3); + offset7 = (stride * 8) - (stride * 3); + + for (i = 0; i < 8; i++) { + gint v1, v2, v3, v; + + v1 = ((p[offset4] - p[offset3]) * 5) + ((p[offset2] - p[offset5]) * 2); + + if (abs(v1) < 80) { + + v2 = ((p[offset2] - p[offset1]) * 5) + ((p[offset0] - p[offset3]) * 2); + v3 = ((p[offset6] - p[offset5]) * 5) + ((p[offset4] - p[offset7]) * 2); + + v = abs(v1) - MIN(abs(v2), abs(v3)); + if (v < 0) + v = 0; + + v2 = (p[offset3] - p[offset4]) / 2; + v3 = (((v * 5) + 32) >> 6) * (((v1 < 0) * 2) - 1); + + if (v2 > 0) + v = MIN(v2, ((v3 < 0) - 1) & v3); + else + v = MAX(v2, ((v3 > 0) - 1) & v3); + } else { + v = 0; + } + + p[offset3] -= v; + p[offset4] += v; + + p++; + } +} + diff --git a/kopete/protocols/msn/webcam/libmimic/decode.c b/kopete/protocols/msn/webcam/libmimic/decode.c new file mode 100644 index 00000000..2bc0e6c9 --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/decode.c @@ -0,0 +1,311 @@ +/* Copyright (C) 2005 Ole André Vadla Ravnås <oleavr@gmail.com> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <string.h> +#include "mimic-private.h" + + +static gboolean decode(MimCtx *ctx, gboolean is_pframe); + +/** + * Decode a MIMIC-encoded frame into RGB data. + * + * @param ctx the mimic context + * @param input_buffer buffer containing the MIMIC-encoded frame to decode + * @param output_buffer buffer that will receive the decoded frame in RGB 24-bpp packed pixel top-down format + * (use #mimic_get_property to determine the required buffer size, as well as frame width and height) + * @returns #TRUE on success + */ +gboolean mimic_decode_frame(MimCtx *ctx, + const guchar *input_buffer, + guchar *output_buffer) +{ + gboolean result, is_pframe; + guchar *input_y, *input_cr, *input_cb; + gint width, height; + + /* + * Some sanity checks. + */ + if (ctx == NULL || input_buffer == NULL || output_buffer == NULL) + { + return FALSE; + } + + if (!ctx->decoder_initialized) + { + return FALSE; + } + + /* + * Get frame dimensions. + */ + width = GUINT16_FROM_LE(*((guint16 *) (input_buffer + 4))); + height = GUINT16_FROM_LE(*((guint16 *) (input_buffer + 6))); + + /* + * Resolution changing is not supported. + */ + if (width != ctx->frame_width || + height != ctx->frame_height) + { + return FALSE; + } + + /* + * Increment frame counter. + */ + ctx->frame_num++; + + /* + * Initialize state. + */ + ctx->quality = GUINT16_FROM_LE(*((guint16 *) (input_buffer + 2))); + is_pframe = GUINT32_FROM_LE(*((guint32 *) (input_buffer + 12))); + ctx->num_coeffs = input_buffer[16]; + + ctx->data_buffer = (gchar *) (input_buffer + 20); + ctx->data_index = 0; + ctx->cur_chunk_len = 16; + ctx->read_odd = FALSE; + + /* + * Decode frame. + */ + if (!(is_pframe && ctx->prev_frame_buf == NULL)) + result = decode(ctx, is_pframe); + else + { + result = FALSE; + } + + /* + * Perform YUV 420 to RGB conversion. + */ + input_y = ctx->cur_frame_buf; + input_cr = ctx->cur_frame_buf + ctx->y_size; + input_cb = ctx->cur_frame_buf + ctx->y_size + ctx->crcb_size; + + _yuv_to_rgb(input_y, + input_cb, + input_cr, + output_buffer, + ctx->frame_width, + ctx->frame_height); + + return result; +} + +/* + * decode_main + * + * Main decoding loop. + */ +static gboolean decode(MimCtx *ctx, gboolean is_pframe) +{ + gint y, x, i, j, chrom_ch, *bptr, base_offset, offset; + gint dct_block[64]; + guchar *src, *dst, *p; + guint32 bit; + + /* + * Clear Cr and Cb planes. + */ + p = ctx->cur_frame_buf + ctx->y_size; + memset(p, 128, 2 * ctx->crcb_size); + + /* + * Decode Y plane. + */ + for (y = 0; y < ctx->num_vblocks_y; y++) { + + base_offset = ctx->y_stride * 8 * y; + + src = ctx->prev_frame_buf + base_offset; + dst = ctx->cur_frame_buf + base_offset; + + for (x = 0; x < ctx->num_hblocks_y; x++) { + + /* Check for a change condition in the current block. */ + + if (is_pframe) + bit = _read_bits(ctx, 1); + else + bit = 0; + + if (bit == 0) { + + /* Yes: Is the new content the same as it was in one of + * the 15 last frames preceding the previous? */ + + if (is_pframe) + bit = _read_bits(ctx, 1); + + if (bit == 0) { + + /* No: decode it. */ + + if (_vlc_decode_block(ctx, dct_block, ctx->num_coeffs) == FALSE) { + + return FALSE; + } + + _idct_dequant_block(ctx, dct_block, 0); + + bptr = dct_block; + for (i = 0; i < 8; i++) { + offset = ctx->y_stride * i; + + for (j = 0; j < 8; j++) { + guint v; + + if (bptr[j] <= 255) + v = (bptr[j] >= 0) ? bptr[j] : 0; + else + v = 255; + + *(dst + offset + j) = v; + } + + bptr += 8; + } + } else { + guint32 backref; + + /* Yes: read the backreference (4 bits) and copy. */ + + backref = _read_bits(ctx, 4); + + p = ctx->buf_ptrs[(ctx->ptr_index + backref) % 16]; + p += base_offset + (x * 8); + + for (i = 0; i < 8; i++) { + offset = ctx->y_stride * i; + + memcpy(dst + offset, p + offset, 8); + } + } + } else { + + /* No change no worries: just copy from the previous frame. */ + + for (i = 0; i < 8; i++) { + offset = ctx->y_stride * i; + + memcpy(dst + offset, src + offset, 8); + } + } + + src += 8; + dst += 8; + } + } + + /* + * Decode Cr and Cb planes. + */ + for (chrom_ch = 0; chrom_ch < 2; chrom_ch++) { + + base_offset = ctx->y_size + (ctx->crcb_size * chrom_ch); + + for (y = 0; y < ctx->num_vblocks_cbcr; y++) { + guint num_rows = 8; + + /* The last row of blocks in chrominance for 160x120 resolution + * is half the normal height and must be accounted for. */ + if (y + 1 == ctx->num_vblocks_cbcr && ctx->frame_height % 16 != 0) + num_rows = 4; + + offset = base_offset + (ctx->crcb_stride * 8 * y); + + src = ctx->prev_frame_buf + offset; + dst = ctx->cur_frame_buf + offset; + + for (x = 0; x < ctx->num_hblocks_cbcr; x++) { + + /* Check for a change condition in the current block. */ + + if (is_pframe) + bit = _read_bits(ctx, 1); + else + bit = 1; + + if (bit == 1) { + + /* Yes: decode it. */ + + if (_vlc_decode_block(ctx, dct_block, ctx->num_coeffs) == FALSE) { + + /* Corrupted frame: clear Cr and Cb planes and return. */ + p = ctx->cur_frame_buf + ctx->y_size; + memset(p, 128, ctx->crcb_size * 2); + + return FALSE; + } + + _idct_dequant_block(ctx, dct_block, 1); + + for (i = 0; i < num_rows; i++) { + p = dst + (ctx->crcb_stride * i); + + for (j = 0; j < 8; j++) + p[j] = dct_block[(i * 8) + j]; + } + + } else { + + /* No change no worries: just copy from the previous frame. */ + + for (i = 0; i < num_rows; i++) { + offset = ctx->crcb_stride * i; + + memcpy(dst + offset, src + offset, 8); + } + } + + src += 8; + dst += 8; + } + } + } + + /* + * Make a copy of the current frame and store in + * the circular pointer list of 16 entries. + */ + ctx->prev_frame_buf = ctx->buf_ptrs[ctx->ptr_index]; + memcpy(ctx->prev_frame_buf, ctx->cur_frame_buf, + ctx->y_size + (ctx->crcb_size * 2)); + + if (--ctx->ptr_index < 0) + ctx->ptr_index = 15; + + /* + * Perform deblocking on all planes. + */ + _deblock(ctx->cur_frame_buf, + ctx->y_stride, ctx->y_row_count); + + _deblock(ctx->cur_frame_buf + ctx->y_size, + ctx->crcb_stride, ctx->crcb_row_count); + + _deblock(ctx->cur_frame_buf + ctx->y_size + ctx->crcb_size, + ctx->crcb_stride, ctx->crcb_row_count); + + return TRUE; +} + diff --git a/kopete/protocols/msn/webcam/libmimic/encode.c b/kopete/protocols/msn/webcam/libmimic/encode.c new file mode 100644 index 00000000..909ebd80 --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/encode.c @@ -0,0 +1,419 @@ +/* Copyright (C) 2005 Ole André Vadla RavnÃ¥s <oleavr@gmail.com> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <stdlib.h> +#include <string.h> +#include <math.h> +#include "mimic-private.h" + +#define LUMINANCE_THRESHOLD 32.0f +#define CHROMINANCE_THRESHOLD 36.0f + +static void encode_main(MimCtx *ctx, guchar *out_buf, gboolean is_pframe); + +/** + * Encode a MIMIC-encoded frame from RGB data. + * + * @param ctx the mimic context + * @param input_buffer buffer containing pixeldata in RGB 24-bpp packed pixel top-down format + * @param output_buffer buffer that will receive the MIMIC-encoded frame + * (use #mimic_get_property to determine the required buffer size) + * @param output_length pointer to an integer that receives the length of the encoded data + * written to output_buffer + * @param make_keyframe whether the encoder should make this frame a keyframe + * @returns #TRUE on success + */ +gboolean mimic_encode_frame(MimCtx *ctx, + const guchar *input_buffer, + guchar *output_buffer, + gint *output_length, + gboolean make_keyframe) +{ + guchar *output_y, *output_cb, *output_cr; + + /* + * Some sanity checks. + */ + if (ctx == NULL || input_buffer == NULL || + output_buffer == NULL || output_length == NULL) + { + return FALSE; + } + + if (!ctx->encoder_initialized) + return FALSE; + + /* + * Initialize state. + */ + ctx->chunk_ptr = (guint32 *) (output_buffer + 20); + ctx->cur_chunk = 0; + ctx->cur_chunk_len = 0; + + if (ctx->frame_num == 0) + make_keyframe = TRUE; + + /* + * Write header. + */ + memset(output_buffer, 0, 20); + *((guint16 *) (output_buffer + 0)) = GUINT16_TO_LE(256); + *((guint16 *) (output_buffer + 2)) = GUINT16_TO_LE(ctx->quality); + *((guint16 *) (output_buffer + 4)) = GUINT16_TO_LE(ctx->frame_width); + *((guint16 *) (output_buffer + 6)) = GUINT16_TO_LE(ctx->frame_height); + *((guint32 *) (output_buffer + 12)) = GUINT32_TO_LE((make_keyframe == 0)); + *(output_buffer + 16) = ctx->num_coeffs; + *(output_buffer + 17) = 0; + + /* + * Perform RGB to YUV 420 conversion. + */ + output_y = ctx->cur_frame_buf; + output_cr = ctx->cur_frame_buf + ctx->y_size; + output_cb = ctx->cur_frame_buf + ctx->y_size + ctx->crcb_size; + + _rgb_to_yuv(input_buffer, + output_y, + output_cb, + output_cr, + ctx->frame_width, + ctx->frame_height); + + /* + * Encode frame. + */ + encode_main(ctx, output_buffer, (make_keyframe == FALSE)); + + /* + * Write out any pending bits to stream by zero-padding with 32 bits. + */ + _write_bits(ctx, 0, 32); + + /* + * Calculate bytes written. + */ + *output_length = (guchar *) ctx->chunk_ptr - output_buffer; + + /* + * Increment frame counter. + */ + ctx->frame_num++; + + return TRUE; +} + +static gdouble compare_blocks(const guchar *p1, + const guchar *p2, + gint stride, + gint row_count, + gboolean is_chrom); + +/* + * encode_main + * + * Main encoding loop. + */ +static void encode_main(MimCtx *ctx, guchar *out_buf, gboolean is_pframe) +{ + gint x, y, i, offset, chrom_ch; + gint dct_block[64]; + guchar *src, *dst, *p1, *p2; + gdouble match; + gboolean encoded; + + /* + * Round down small differences in luminance channel. + */ + if (is_pframe) { + + p1 = ctx->cur_frame_buf; + p2 = ctx->prev_frame_buf; + + for (i = 0; i < ctx->y_size; i++) { + + if (abs(p2[0] - p1[0]) < 7) + p1[0] = p2[0]; + + p1++; + p2++; + } + } + + /* + * Encode Y plane. + */ + for (y = 0; y < ctx->num_vblocks_y; y++) { + + for (x = 0; x < ctx->num_hblocks_y; x++) { + + /* Calculate final offset into buffer. */ + offset = (ctx->y_stride * 8 * y) + (x * 8); + + src = NULL; + encoded = FALSE; + + if (is_pframe) { + + /* Is the current block similar enough to what it was in the previous frame? */ + + match = compare_blocks(ctx->cur_frame_buf + offset, + ctx->prev_frame_buf + offset, + ctx->y_stride, 8, + FALSE); + + if (match > LUMINANCE_THRESHOLD) { + + /* Yes: write out '1' to indicate a no-change condition. */ + + _write_bits(ctx, 1, 1); + + src = ctx->prev_frame_buf + offset; + encoded = TRUE; + + } else { + + /* No: Is the current block similar enough to what it was in one + * of the (up to) 15 last frames preceding the previous? */ + + gint best_index = 0; + gdouble best_match = 0.0; + + gint num_backrefs = ctx->frame_num - 1; + if (num_backrefs > 15) + num_backrefs = 15; + + for (i = 1; i <= num_backrefs; i++) { + + match = compare_blocks(ctx->buf_ptrs[(ctx->ptr_index + i) % 16] + offset, + ctx->cur_frame_buf + offset, + ctx->y_stride, 8, + FALSE); + + if (match > LUMINANCE_THRESHOLD && match > best_match) { + best_index = i; + best_match = match; + } + + } + + if (best_index != 0) { + + /* Yes: write out '01' to indicate a "change but like previous"-condition, + * followed by 4 bits containing the back-reference. */ + _write_bits(ctx, 0, 1); + _write_bits(ctx, 1, 1); + _write_bits(ctx, best_index, 4); + + src = ctx->buf_ptrs[(ctx->ptr_index + best_index) % 16] + offset; + encoded = TRUE; + + } + } + } + + if (!encoded) { + + /* Keyframe or in any case no? ;-) Well, encode it then. */ + + if (is_pframe) { + _write_bits(ctx, 0, 1); + _write_bits(ctx, 0, 1); + } + + _fdct_quant_block(ctx, + dct_block, + ctx->cur_frame_buf + offset, + ctx->y_stride, + FALSE, + ctx->num_coeffs); + + _vlc_encode_block(ctx, + dct_block, + ctx->num_coeffs); + + } + + /* And if there was some kind of no-change condition, + * we want to copy the previous block. */ + if (src != NULL) { + + dst = ctx->cur_frame_buf + offset; + for (i = 0; i < 8; i++) { + + memcpy(dst, src, 8); + + src += ctx->y_stride; + dst += ctx->y_stride; + } + + } + + } + + } + + /* + * Encode Cr and Cb planes. + */ + for (chrom_ch = 0; chrom_ch < 2; chrom_ch++) { + + /* Calculate base offset into buffer. */ + gint base_offset = ctx->y_size + (ctx->crcb_size * chrom_ch); + + for (y = 0; y < ctx->num_vblocks_cbcr; y++) { + guchar tmp_block[64]; + guint num_rows = 8; + + /* The last row of blocks in chrominance for 160x120 resolution + * is half the normal height and must be accounted for. */ + if (y + 1 == ctx->num_vblocks_cbcr && ctx->frame_height % 16 != 0) + num_rows = 4; + + for (x = 0; x < ctx->num_hblocks_cbcr; x++) { + + /* Calculate final offset into buffer. */ + offset = base_offset + (ctx->crcb_stride * 8 * y) + (x * 8); + + src = NULL; + encoded = FALSE; + + if (is_pframe) { + + /* Is the current block similar enough to what it was in the previous frame? */ + + match = compare_blocks(ctx->prev_frame_buf + offset, + ctx->cur_frame_buf + offset, + ctx->crcb_stride, num_rows, + TRUE); + + if (match > CHROMINANCE_THRESHOLD) { + + /* Yes: write out '0' to indicate a no-change condition. */ + + _write_bits(ctx, 0, 1); + + encoded = TRUE; + + src = ctx->prev_frame_buf + offset; + dst = ctx->cur_frame_buf + offset; + for (i = 0; i < num_rows; i++) { + + memcpy(dst, src, 8); + + src += ctx->crcb_stride; + dst += ctx->crcb_stride; + } + } + + } + + if (!encoded) { + + /* Keyframe or just not similar enough? ;-) Well, encode it then. */ + + if (is_pframe) + _write_bits(ctx, 1, 1); + + /* Use a temporary array to handle cases where the + * current block is not of normal height (see above). */ + src = ctx->cur_frame_buf + offset; + dst = tmp_block; + for (i = 0; i < 8; i++) { + + memcpy(dst, src, 8); + + if (i < (num_rows - 1)) + src += ctx->crcb_stride; + dst += 8; + } + + _fdct_quant_block(ctx, + dct_block, + tmp_block, + 8, + TRUE, + ctx->num_coeffs); + + _vlc_encode_block(ctx, + dct_block, + ctx->num_coeffs); + + } + + } + + } + + } + + /* + * Make a copy of the current frame and store in + * the circular pointer list of 16 entries. + */ + ctx->prev_frame_buf = ctx->buf_ptrs[ctx->ptr_index]; + memcpy(ctx->prev_frame_buf, ctx->cur_frame_buf, + ctx->y_size + (ctx->crcb_size * 2)); + + if (--ctx->ptr_index < 0) + ctx->ptr_index = 15; +} + +/* + * compare_blocks + * + * Helper-function used to compare two blocks and + * determine how similar they are. + */ +static gdouble compare_blocks(const guchar *p1, + const guchar *p2, + gint stride, + gint row_count, + gboolean is_chrom) +{ + gint i, j, sum; + gdouble d; + + sum = 0; + + for (i = 0; i < row_count; i++) { + + for (j = 0; j < 8; j++) { + + gint d = p2[j] - p1[j]; + + sum += d * d; + } + + p1 += stride; + p2 += stride; + } + + if (is_chrom) { + if (row_count == 8) + d = sum * 0.015625; + else + d = sum * 0.03125; + } else { + d = sum / 64; + } + + if (d == 0.0f) + return 100.0f; + else + return (10.0f * log(65025.0f / d)) / G_LN10; +} + diff --git a/kopete/protocols/msn/webcam/libmimic/fdct_quant.c b/kopete/protocols/msn/webcam/libmimic/fdct_quant.c new file mode 100644 index 00000000..7e8d0bdd --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/fdct_quant.c @@ -0,0 +1,181 @@ +/* Copyright (C) 2005 Ole André Vadla RavnÃ¥s <oleavr@gmail.com> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "mimic-private.h" + +extern guchar _col_zag[64]; + +void _fdct_quant_block(MimCtx *ctx, gint *block, const guchar *src, + gint stride, gboolean is_chrom, gint num_coeffs) +{ + gint sum1, sum2, sum3, sum4; + gint diff1, diff2, diff3, diff4; + gint ex1, ex2, ex3, ex4, ex5; + gint i, j; + const guchar *p1; + gint *iptr; + + /* + * Forward DCT, first pass (horizontal). + */ + p1 = src; + iptr = block; + + for (i = 0; i < 8; i++) { + sum1 = p1[0] + p1[7]; + sum2 = p1[1] + p1[6]; + sum3 = p1[2] + p1[5]; + sum4 = p1[3] + p1[4]; + + diff1 = p1[0] - p1[7]; + diff2 = p1[1] - p1[6]; + diff3 = p1[2] - p1[5]; + diff4 = p1[3] - p1[4]; + + ex1 = ((diff1 + diff4) * 851) - (diff1 * 282); + ex2 = ((diff2 + diff3) * 1004) - (diff2 * 804); + ex3 = ((diff2 + diff3) * 1004) - (diff3 * 1204); + ex4 = ((diff1 + diff4) * 851) - (diff4 * 1420); + + iptr[0] = sum1 + sum2 + sum3 + sum4; + iptr[2] = (((sum1 - sum4) * 1337) + ((sum2 - sum3) * 554)) >> 10; + iptr[4] = sum1 - sum2 - sum3 + sum4; + + iptr[1] = (ex1 + ex2 + ex3 + ex4) >> 10; + iptr[3] = ((ex4 - ex2) * 181) >> 17; + iptr[5] = ((ex1 - ex3) * 181) >> 17; + + p1 += stride; + iptr += 8; + } + + p1 = src; + iptr = block; + + /* + * Forward DCT, first pass (vertical). + * + * This is only known to be correct for i == 0, though it seems to be ... + */ + for (i = 0; i < 6; i++) { + sum1 = iptr[ 0 + i] + iptr[56 + i]; + sum2 = iptr[ 8 + i] + iptr[48 + i]; + sum3 = iptr[16 + i] + iptr[40 + i]; + sum4 = iptr[24 + i] + iptr[32 + i]; + + diff1 = iptr[ 0 + i] - iptr[56 + i]; + diff2 = iptr[ 8 + i] - iptr[48 + i]; + diff3 = iptr[16 + i] - iptr[40 + i]; + diff4 = iptr[24 + i] - iptr[32 + i]; + + ex1 = ((diff1 + diff4) * 851) - (diff1 * 282); + ex2 = ((diff2 + diff3) * 1004) - (diff2 * 804); + ex3 = ((diff2 + diff3) * 1004) - (diff3 * 1204); + ex4 = ((diff1 + diff4) * 851) - (diff4 * 1420); + + ex5 = (sum1 + sum2 - sum3 - sum4) * 554; + + for (j = 0; j < 7 - i; j++) { + switch (j) { + + case 0: + iptr[ 0 + i] = (16 + sum1 + sum2 + sum3 + sum4) >> 5; + break; + + case 1: + iptr[ 8 + i] = (16384 + ex1 + ex2 + ex3 + ex4) >> 15; + break; + + case 2: + iptr[16 + i] = (16384 + ((sum1 - sum4) * 783) + ex5) >> 15; + break; + + case 3: + iptr[24 + i] = (8192 + (((ex4 - ex2) >> 8) * 181)) >> 14; + break; + + case 4: + iptr[32 + i] = (16 + sum1 - sum2 - sum3 + sum4) >> 5; + break; + + case 5: + iptr[40 + i] = (8192 + (((ex1 - ex3) >> 8) * 181)) >> 14; + break; + + case 6: + iptr[48 + i] = (16384 - ((sum2 - sum3) * 1891) + ex5) >> 15; + break; + } + } + } + + /* + * Quantize. + */ + block[0] /= 2; + block[8] /= 4; + block[1] /= 4; + block[6] = 0; + + if (num_coeffs > 3) { + + gdouble s = (10000 - ctx->quality) * 10.0 * (gfloat) 9.9999997e-5; + + if (s > 10.0) + s = 10.0; + else if (is_chrom != 0 && s < 1.0) + s = 1.0; + else if (s < 2.0) + s = 2.0; + + s = 1.0 / s; + + for (i = 3; i < num_coeffs; i++) { + + gdouble coeff, r; + + coeff = block[_col_zag[i]] * s; + r = coeff - (gint) coeff; + + if (r >= 0.6) + block[_col_zag[i]] = (gint) (coeff + 1.0); + else if (r <= -0.6) + block[_col_zag[i]] = (gint) (coeff - 1.0); + else + block[_col_zag[i]] = (gint) coeff; + + if (block[_col_zag[i]] > 120) + block[_col_zag[i]] = 120; + else if (block[_col_zag[i]] < -120) + block[_col_zag[i]] = -120; + } + } + + if (block[8] > 120) + block[8] = 120; + else if (block[8] < -120) + block[8] = -120; + + if (block[1] > 120) + block[1] = 120; + else if (block[1] < -120) + block[1] = -120; + + for (i = num_coeffs; i < 64; i++) + block[_col_zag[i]] = 0; +} + diff --git a/kopete/protocols/msn/webcam/libmimic/idct_dequant.c b/kopete/protocols/msn/webcam/libmimic/idct_dequant.c new file mode 100644 index 00000000..e5d64fb4 --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/idct_dequant.c @@ -0,0 +1,134 @@ +/* Copyright (C) 2005 Ole André Vadla Ravnås <oleavr@gmail.com> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "mimic-private.h" + +void _idct_dequant_block(MimCtx *ctx, gint *block, gboolean is_chrom) +{ + gdouble f; + gint i, *p; + + /* + * De-quantize. + */ + f = (10000 - ctx->quality) * 10.0 * (gfloat) 9.9999997e-5; + + if (f > 10.0) + f = 10.0; + + if (!is_chrom) { + if (f < 2.0) + f = 2.0; + } else { + if (f < 1.0) + f = 1.0; + } + + block[0] <<= 1; + block[1] <<= 2; + block[8] <<= 2; + + for (i = 2; i < 64; i++) { + if (i == 8) + continue; + + block[i] *= f; + } + + /* + * Inverse DCT, first pass (horizontal). + */ + p = block; + + for (i = 0; i < 8; i++) { + gint v1, v2, v3, v4, v5, v6, v7, v8; + gint va, vb; + + va = (p[0] << 11) + (p[4] << 11); + vb = ((p[2] << 2) * 392) + (((p[2] << 2) + (p[6] << 2)) * 277); + v1 = va + vb + 512; + v2 = va - vb + 512; + + va = (p[0] << 11) - (p[4] << 11); + vb = (((p[2] << 2) + (p[6] << 2)) * 277) - ((p[6] << 2) * 946); + v3 = va + vb + 512; + v4 = va - vb + 512; + + va = (p[1] << 9) + (p[3] * 724) + (p[7] << 9); + vb = (p[1] << 9) + (p[5] * 724) - (p[7] << 9); + v5 = (((va + vb) * 213) - (vb * 71)) >> 6; + v6 = (((va + vb) * 213) - (va * 355)) >> 6; + + va = (p[1] << 9) - (p[3] * 724) + (p[7] << 9); + vb = (p[1] << 9) - (p[5] * 724) - (p[7] << 9); + v7 = (((va + vb) * 251) - (va * 201)) >> 6; + v8 = (((va + vb) * 251) - (vb * 301)) >> 6; + + p[0] = (v1 + v5) >> 10; + p[1] = (v3 + v7) >> 10; + p[2] = (v4 + v8) >> 10; + p[3] = (v2 + v6) >> 10; + p[4] = (v2 - v6) >> 10; + p[5] = (v4 - v8) >> 10; + p[6] = (v3 - v7) >> 10; + p[7] = (v1 - v5) >> 10; + + p += 8; + } + + /* + * Inverse dct, second pass (vertical). + */ + p = block; + + for (i = 0; i < 8; i++) { + gint v1, v2, v3, v4, v5, v6, v7, v8; + gint va, vb; + + va = (p[0] << 9) + (p[32] << 9); + vb = ((p[16] + p[48]) * 277) + (p[16] * 392); + v1 = va + vb + 1024; + v2 = va - vb + 1024; + + va = (p[0] << 9) - (p[32] << 9); + vb = ((p[16] + p[48]) * 277) - (p[48] * 946); + v3 = va + vb + 1024; + v4 = va - vb + 1024; + + va = ((p[8] << 7) + (p[24] * 181) + (p[56] << 7)) >> 6; + vb = ((p[8] << 7) + (p[40] * 181) - (p[56] << 7)) >> 6; + v5 = ((va + vb) * 213) - (vb * 71); + v6 = ((va + vb) * 213) - (va * 355); + + va = ((p[8] << 7) - (p[24] * 181) + (p[56] << 7)) >> 6; + vb = ((p[8] << 7) - (p[40] * 181) - (p[56] << 7)) >> 6; + v7 = ((va + vb) * 251) - (va * 201); + v8 = ((va + vb) * 251) - (vb * 301); + + p[0] = (v1 + v5) >> 11; + p[8] = (v3 + v7) >> 11; + p[16] = (v4 + v8) >> 11; + p[24] = (v2 + v6) >> 11; + p[32] = (v2 - v6) >> 11; + p[40] = (v4 - v8) >> 11; + p[48] = (v3 - v7) >> 11; + p[56] = (v1 - v5) >> 11; + + p++; + } +} + diff --git a/kopete/protocols/msn/webcam/libmimic/mimic-private.h b/kopete/protocols/msn/webcam/libmimic/mimic-private.h new file mode 100644 index 00000000..d33c50b7 --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/mimic-private.h @@ -0,0 +1,117 @@ +/* Copyright (C) 2005 Ole André Vadla RavnÃ¥s <oleavr@gmail.com> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef MIMIC_PRIVATE_H +#define MIMIC_PRIVATE_H + +#include "mimic.h" + +#define ENCODER_BUFFER_SIZE 16384 +#define ENCODER_QUALITY_DEFAULT 0 +#define ENCODER_QUALITY_MIN 0 +#define ENCODER_QUALITY_MAX 10000 + +struct _MimCtx { + gboolean encoder_initialized; + gboolean decoder_initialized; + + gint frame_width; + gint frame_height; + gint quality; + gint num_coeffs; + + gint y_stride; + gint y_row_count; + gint y_size; + + gint crcb_stride; + gint crcb_row_count; + gint crcb_size; + + gint num_vblocks_y; + gint num_hblocks_y; + + gint num_vblocks_cbcr; + gint num_hblocks_cbcr; + + guchar *cur_frame_buf; + guchar *prev_frame_buf; + + gint8 vlcdec_lookup[2296]; + + gchar *data_buffer; + guint data_index; + + guint32 cur_chunk; + gint cur_chunk_len; + + guint32 *chunk_ptr; + gboolean read_odd; + + gint frame_num; + + gint ptr_index; + guchar *buf_ptrs[16]; +}; + +typedef struct { + guchar length1; + guint32 part1; + + guchar length2; + guint32 part2; +} VlcSymbol; + +typedef struct { + guint32 magic; + guchar pos_add; + guchar num_bits; +} VlcMagic; + +void _mimic_init(MimCtx *ctx, gint width, gint height); +guchar _clamp_value(gint value); + +guint32 _read_bits(MimCtx *ctx, gint num_bits); +void _write_bits(MimCtx *ctx, guint32 bits, gint length); + +void _vlc_encode_block(MimCtx *ctx, const gint *block, gint num_coeffs); +gboolean _vlc_decode_block(MimCtx *ctx, gint *block, gint num_coeffs); + +void _fdct_quant_block(MimCtx *ctx, gint *block, const guchar *src, + gint stride, gboolean is_chrom, gint num_coeffs); +void _idct_dequant_block(MimCtx *ctx, gint *block, gboolean is_chrom); + +VlcMagic *_find_magic(guint magic); +void _initialize_vlcdec_lookup(gint8 *lookup_tbl); + +void _rgb_to_yuv(const guchar *input_rgb, + guchar *output_y, + guchar *output_cb, + guchar *output_cr, + gint width, + gint height); +void _yuv_to_rgb(const guchar *input_y, + const guchar *input_cb, + const guchar *input_cr, + guchar *output_rgb, + guint width, + guint height); + +void _deblock(guchar *blocks, guint stride, guint row_count); + +#endif + diff --git a/kopete/protocols/msn/webcam/libmimic/mimic.c b/kopete/protocols/msn/webcam/libmimic/mimic.c new file mode 100644 index 00000000..95564755 --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/mimic.c @@ -0,0 +1,334 @@ +/* Copyright (C) 2005 Ole André Vadla RavnÃ¥s <oleavr@gmail.com> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <string.h> +#include "mimic-private.h" + +/** + * Creates a new instance and returns a pointer to the new context + * that can be used for either encoding or decoding by calling + * #mimic_encoder_init or #mimic_decoder_init. + * + * #mimic_close is called to free any resources associated with + * the context once done. + * + * @returns a new mimic context + */ +MimCtx *mimic_open() +{ + MimCtx *ctx; + + ctx = g_new0(MimCtx, 1); + + ctx->encoder_initialized = FALSE; + ctx->decoder_initialized = FALSE; + + return ctx; +} + +/** + * Frees any resources associated with the given context. + * + * @param ctx the mimic context to free + */ +void mimic_close(MimCtx *ctx) +{ + if (ctx->encoder_initialized || ctx->decoder_initialized) { + gint i; + + g_free(ctx->cur_frame_buf); + + for (i = 0; i < 16; i++) + g_free(ctx->buf_ptrs[i]); + } + + g_free(ctx); +} + +/* + * mimic_init + * + * Internal helper-function used to initialize + * a given context. + */ +static void mimic_init(MimCtx *ctx, gint width, gint height) +{ + gint bufsize, i; + + /* + * Dimensions-related. + */ + ctx->frame_width = width; + ctx->frame_height = height; + + ctx->y_stride = ctx->frame_width; + ctx->y_row_count = ctx->frame_height; + ctx->y_size = ctx->y_stride * ctx->y_row_count; + + ctx->crcb_stride = ctx->y_stride / 2; + ctx->crcb_row_count = ctx->y_row_count / 2; + ctx->crcb_size = ctx->crcb_stride * ctx->crcb_row_count; + + ctx->num_vblocks_y = ctx->frame_height / 8; + ctx->num_hblocks_y = ctx->frame_width / 8; + + ctx->num_vblocks_cbcr = ctx->frame_height / 16; + ctx->num_hblocks_cbcr = ctx->frame_width / 16; + + if (ctx->frame_height % 16 != 0) + ctx->num_vblocks_cbcr++; + + /* + * Initialize state. + */ + ctx->frame_num = 0; + ctx->ptr_index = 15; + ctx->num_coeffs = 28; + + /* + * Allocate memory for buffers. + */ + ctx->cur_frame_buf = g_new(guchar, (320 * 240 * 3) / 2); + + bufsize = ctx->y_size + (ctx->crcb_size * 2); + for (i = 0; i < 16; i++) + ctx->buf_ptrs[i] = g_new(guchar, bufsize); + + /* + * Initialize vlc lookup used by decoder. + */ + _initialize_vlcdec_lookup(ctx->vlcdec_lookup); +} + +/** + * Initialize the mimic encoder and prepare for encoding by + * initializing internal state and allocating resources as + * needed. + * + * After initializing use #mimic_get_property to determine + * the size of the output buffer needed for calls to + * #mimic_encode_frame. Use #mimic_set_property to set + * encoding quality. + * + * Note that once a given context has been initialized + * for either encoding or decoding it is not possible + * to initialize it again. + * + * @param ctx the mimic context to initialize + * @param resolution a #MimicResEnum used to specify the resolution + * @returns #TRUE on success + */ +gboolean mimic_encoder_init(MimCtx *ctx, const MimicResEnum resolution) +{ + gint width, height; + + /* Check if we've been initialized before. */ + if (ctx->encoder_initialized || ctx->decoder_initialized) + return FALSE; + + /* Check resolution. */ + if (resolution == MIMIC_RES_LOW) { + width = 160; + height = 120; + } else if (resolution == MIMIC_RES_HIGH) { + width = 320; + height = 240; + } else { + return FALSE; + } + + /* Initialize! */ + mimic_init(ctx, width, height); + + /* Set a default quality setting. */ + ctx->quality = ENCODER_QUALITY_DEFAULT; + + ctx->encoder_initialized = TRUE; + + return TRUE; +} + +/** + * Initialize the mimic decoder. The frame passed in frame_buffer + * is used to determine the resolution so that the internal state + * can be prepared and resources allocated accordingly. Note that + * the frame passed has to be a keyframe. + * + * After initializing use #mimic_get_property to determine required + * buffer-size, resolution, quality, etc. + * + * Note that once a given context has been initialized + * for either encoding or decoding it is not possible + * to initialize it again. + * + * @param ctx the mimic context to initialize + * @param frame_buffer buffer containing the first frame to decode + * @returns #TRUE on success + */ +gboolean mimic_decoder_init(MimCtx *ctx, const guchar *frame_buffer) +{ + gint width, height; + gboolean is_keyframe; + + /* Check if we've been initialized before and that + * frame_buffer is not NULL. */ + if (ctx->encoder_initialized || ctx->decoder_initialized || + frame_buffer == NULL) + { + return FALSE; + } + + /* Check resolution. */ + width = GUINT16_FROM_LE(*((guint16 *) (frame_buffer + 4))); + height = GUINT16_FROM_LE(*((guint16 *) (frame_buffer + 6))); + + if (!(width == 160 && height == 120) && !(width == 320 && height == 240)) + return FALSE; + + /* Check that we're initialized with a keyframe. */ + is_keyframe = (GUINT32_FROM_LE(*((guint32 *) (frame_buffer + 12))) == 0); + + if (!is_keyframe) + return FALSE; + + /* Get quality setting (in case we get queried for it before decoding). */ + ctx->quality = GUINT16_FROM_LE(*((guint16 *) (frame_buffer + 2))); + + /* Initialize! */ + mimic_init(ctx, width, height); + + ctx->decoder_initialized = TRUE; + + return TRUE; +} + +/** + * Get a property from a given mimic context. The context + * has to be initialized. + * + * Currently the following properties are defined: + * - "buffer_size" + * - Required output buffer size + * - "width" + * - Frame width + * - "height" + * - Frame height + * - "quality" + * - Encoder: Encoding quality used + * - Decoder: Decoding quality of the last known frame + * + * @param ctx the mimic context to retrieve the property from + * @param name of the property to retrieve the current value of + * @param data pointer to the data that will receive the retrieved value + * @returns #TRUE on success + */ +gboolean mimic_get_property(MimCtx *ctx, const gchar *name, gpointer data) +{ + /* Either the encoder or the decoder has to be initialized. */ + if (!ctx->encoder_initialized && !ctx->decoder_initialized) + return FALSE; + + if (ctx->encoder_initialized) { + + if (strcmp(name, "buffer_size") == 0) { + *((gint *) data) = ENCODER_BUFFER_SIZE; + + return TRUE; + } + + } else { /* decoder_initialized */ + + if (strcmp(name, "buffer_size") == 0) { + *((gint *) data) = ctx->frame_width * ctx->frame_height * 3; + + return TRUE; + } + } + + if (strcmp(name, "width") == 0) { + *((gint *) data) = ctx->frame_width; + + return TRUE; + } else if (strcmp(name, "height") == 0) { + *((gint *) data) = ctx->frame_height; + + return TRUE; + } else if (strcmp(name, "quality") == 0) { + *((gint *) data) = ctx->quality; + + return TRUE; + } + + return FALSE; +} + +/** + * Set a property in a given mimic context. The context + * has to be initialized. + * + * Currently the following properties are defined: + * - "quality" + * - Encoding quality used by encoder. + * + * @param ctx the mimic context to set a property in + * @param name of the property to set to a new value + * @param data pointer to the data that contains the new value + * @returns #TRUE on success + */ +gboolean mimic_set_property(MimCtx *ctx, const gchar *name, gpointer data) +{ + /* Either the encoder or the decoder has to be initialized. */ + if (!ctx->encoder_initialized && !ctx->decoder_initialized) + return FALSE; + + if (ctx->encoder_initialized) { + + if (strcmp(name, "quality") == 0) { + gint new_quality = *((gint *) data); + + if (new_quality < ENCODER_QUALITY_MIN || + new_quality > ENCODER_QUALITY_MAX) + { + return FALSE; + } + + ctx->quality = new_quality; + + return TRUE; + } + + } else { /* decoder_initialized */ } + + return FALSE; +} + +/* + * _clamp_value + * + * Internal helper-function used to clamp a given + * value to the range [ 0, 255 ]. + */ +guchar _clamp_value(gint value) +{ + if (value < 0) + return 0; + else if (value > 255) + return 255; + else + return value; +} + diff --git a/kopete/protocols/msn/webcam/libmimic/mimic.h b/kopete/protocols/msn/webcam/libmimic/mimic.h new file mode 100644 index 00000000..491548f4 --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/mimic.h @@ -0,0 +1,73 @@ +/* Copyright (C) 2005 Ole André Vadla RavnÃ¥s <oleavr@gmail.com> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef MIMIC_H +#define MIMIC_H + +#include <glib.h> + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * @defgroup libmimic libmimic public API + * @brief The public API of the libmimic library + * + * libmimic provides the API required for encoding and decoding + * MIMIC v2.x-encoded content. + * + * @{ + */ + +/** + * The mimic encoding/decoding context returned by #mimic_open + * and used for all further API calls until #mimic_close. + */ +typedef struct _MimCtx MimCtx; + +typedef enum { + MIMIC_RES_LOW, /**< 160x120 resolution */ + MIMIC_RES_HIGH /**< 320x240 resolution */ +} MimicResEnum; + +MimCtx *mimic_open(); +void mimic_close(MimCtx *ctx); + +gboolean mimic_encoder_init(MimCtx *ctx, const MimicResEnum resolution); +gboolean mimic_decoder_init(MimCtx *ctx, const guchar *frame_buffer); + +gboolean mimic_get_property(MimCtx *ctx, const gchar *name, gpointer data); +gboolean mimic_set_property(MimCtx *ctx, const gchar *name, gpointer data); + +gboolean mimic_encode_frame(MimCtx *ctx, + const guchar *input_buffer, + guchar *output_buffer, + gint *output_length, + gboolean make_keyframe); +gboolean mimic_decode_frame(MimCtx *ctx, + const guchar *input_buffer, + guchar *output_buffer); + +/** @} */ + +#ifdef __cplusplus +} +#endif + +#endif + diff --git a/kopete/protocols/msn/webcam/libmimic/query.c b/kopete/protocols/msn/webcam/libmimic/query.c new file mode 100644 index 00000000..8b137891 --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/query.c @@ -0,0 +1 @@ + diff --git a/kopete/protocols/msn/webcam/libmimic/vlc_common.c b/kopete/protocols/msn/webcam/libmimic/vlc_common.c new file mode 100644 index 00000000..cbb0acc5 --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/vlc_common.c @@ -0,0 +1,1364 @@ +/* Copyright (C) 2005 Ole André Vadla RavnÃ¥s <oleavr@gmail.com> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <stdlib.h> +#include "mimic-private.h" + +guchar _col_zag[64] = { + 0, 8, 1, 2, 9, 16, 24, 17, + 10, 3, 4, 11, 18, 25, 32, 40, + 33, 26, 19, 12, 5, 6, 13, 20, + 27, 34, 41, 48, 56, 49, 42, 35, + 28, 21, 14, 7, 15, 22, 29, 36, + 43, 50, 57, 58, 51, 44, 37, 30, + 23, 31, 38, 45, 52, 59, 39, 46, + 53, 60, 61, 54, 47, 55, 62, 63 +}; + +VlcSymbol _vlc_alphabet[16][128] = { + + /* + * base alphabet - no zeroes prefixed + */ + { + { 3, 0x1, 0, 0 }, { 4, 0x7, 0, 0 }, + { 4, 0x5, 0, 0 }, { 6, 0x27, 0, 0 }, + { 6, 0x25, 0, 0 }, { 6, 0x23, 0, 0 }, + { 6, 0x21, 0, 0 }, { 8, 0xcf, 0, 0 }, + { 8, 0xcd, 0, 0 }, { 8, 0xcb, 0, 0 }, + { 8, 0xc9, 0, 0 }, { 8, 0xc7, 0, 0 }, + { 8, 0xc5, 0, 0 }, { 8, 0xc3, 0, 0 }, + { 8, 0xc1, 0, 0 }, { 10, 0x35f, 0, 0 }, + { 10, 0x35d, 0, 0 }, { 10, 0x35b, 0, 0 }, + { 10, 0x359, 0, 0 }, { 10, 0x357, 0, 0 }, + { 10, 0x355, 0, 0 }, { 10, 0x353, 0, 0 }, + { 10, 0x351, 0, 0 }, { 10, 0x34f, 0, 0 }, + { 10, 0x34d, 0, 0 }, { 10, 0x34b, 0, 0 }, + { 10, 0x349, 0, 0 }, { 10, 0x347, 0, 0 }, + { 10, 0x345, 0, 0 }, { 10, 0x343, 0, 0 }, + { 10, 0x341, 0, 0 }, { 12, 0xeff, 0, 0 }, + { 12, 0xefd, 0, 0 }, { 12, 0xefb, 0, 0 }, + { 12, 0xef9, 0, 0 }, { 12, 0xef7, 0, 0 }, + { 12, 0xef5, 0, 0 }, { 12, 0xef3, 0, 0 }, + { 12, 0xef1, 0, 0 }, { 12, 0xeef, 0, 0 }, + { 12, 0xeed, 0, 0 }, { 12, 0xeeb, 0, 0 }, + { 12, 0xee9, 0, 0 }, { 12, 0xee7, 0, 0 }, + { 12, 0xee5, 0, 0 }, { 12, 0xee3, 0, 0 }, + { 12, 0xee1, 0, 0 }, { 12, 0xedf, 0, 0 }, + { 12, 0xedd, 0, 0 }, { 12, 0xedb, 0, 0 }, + { 12, 0xed9, 0, 0 }, { 12, 0xed7, 0, 0 }, + { 12, 0xed5, 0, 0 }, { 12, 0xed3, 0, 0 }, + { 12, 0xed1, 0, 0 }, { 12, 0xecf, 0, 0 }, + { 12, 0xecd, 0, 0 }, { 12, 0xecb, 0, 0 }, + { 12, 0xec9, 0, 0 }, { 12, 0xec7, 0, 0 }, + { 12, 0xec5, 0, 0 }, { 12, 0xec3, 0, 0 }, + { 12, 0xec1, 0, 0 }, { 17, 0x1fd7f, 0, 0 }, + { 17, 0x1fd7d, 0, 0 }, { 17, 0x1fd7b, 0, 0 }, + { 17, 0x1fd79, 0, 0 }, { 17, 0x1fd77, 0, 0 }, + { 17, 0x1fd75, 0, 0 }, { 17, 0x1fd73, 0, 0 }, + { 17, 0x1fd71, 0, 0 }, { 17, 0x1fd6f, 0, 0 }, + { 17, 0x1fd6d, 0, 0 }, { 17, 0x1fd6b, 0, 0 }, + { 17, 0x1fd69, 0, 0 }, { 17, 0x1fd67, 0, 0 }, + { 17, 0x1fd65, 0, 0 }, { 17, 0x1fd63, 0, 0 }, + { 17, 0x1fd61, 0, 0 }, { 17, 0x1fd5f, 0, 0 }, + { 17, 0x1fd5d, 0, 0 }, { 17, 0x1fd5b, 0, 0 }, + { 17, 0x1fd59, 0, 0 }, { 17, 0x1fd57, 0, 0 }, + { 17, 0x1fd55, 0, 0 }, { 17, 0x1fd53, 0, 0 }, + { 17, 0x1fd51, 0, 0 }, { 17, 0x1fd4f, 0, 0 }, + { 17, 0x1fd4d, 0, 0 }, { 17, 0x1fd4b, 0, 0 }, + { 17, 0x1fd49, 0, 0 }, { 17, 0x1fd47, 0, 0 }, + { 17, 0x1fd45, 0, 0 }, { 17, 0x1fd43, 0, 0 }, + { 17, 0x1fd41, 0, 0 }, { 17, 0x1fd3f, 0, 0 }, + { 17, 0x1fd3d, 0, 0 }, { 17, 0x1fd3b, 0, 0 }, + { 17, 0x1fd39, 0, 0 }, { 17, 0x1fd37, 0, 0 }, + { 17, 0x1fd35, 0, 0 }, { 17, 0x1fd33, 0, 0 }, + { 17, 0x1fd31, 0, 0 }, { 17, 0x1fd2f, 0, 0 }, + { 17, 0x1fd2d, 0, 0 }, { 17, 0x1fd2b, 0, 0 }, + { 17, 0x1fd29, 0, 0 }, { 17, 0x1fd27, 0, 0 }, + { 17, 0x1fd25, 0, 0 }, { 17, 0x1fd23, 0, 0 }, + { 17, 0x1fd21, 0, 0 }, { 17, 0x1fd1f, 0, 0 }, + { 17, 0x1fd1d, 0, 0 }, { 17, 0x1fd1b, 0, 0 }, + { 17, 0x1fd19, 0, 0 }, { 17, 0x1fd17, 0, 0 }, + { 17, 0x1fd15, 0, 0 }, { 17, 0x1fd13, 0, 0 }, + { 17, 0x1fd11, 0, 0 }, { 17, 0x1fd0f, 0, 0 }, + { 17, 0x1fd0d, 0, 0 }, { 17, 0x1fd0b, 0, 0 }, + { 17, 0x1fd09, 0, 0 }, { 17, 0x1fd07, 0, 0 }, + { 17, 0x1fd05, 0, 0 }, { 17, 0x1fd03, 0, 0 }, + { 17, 0x1fd01, 0, 0 }, { 17, 0x1fd01, 0, 0 } + }, + + /* + * prefixed with 1 zero + */ + { + { 5, 0x17, 0, 0 }, { 8, 0xe7, 0, 0 }, + { 8, 0xe5, 0, 0 }, { 9, 0x1d7, 0, 0 }, + { 9, 0x1d5, 0, 0 }, { 9, 0x1d3, 0, 0 }, + { 9, 0x1d1, 0, 0 }, { 12, 0xf8f, 0, 0 }, + { 12, 0xf8d, 0, 0 }, { 12, 0xf8b, 0, 0 }, + { 12, 0xf89, 0, 0 }, { 12, 0xf87, 0, 0 }, + { 12, 0xf85, 0, 0 }, { 12, 0xf83, 0, 0 }, + { 12, 0xf81, 0, 0 }, { 15, 0x7f1f, 0, 0 }, + { 15, 0x7f1d, 0, 0 }, { 15, 0x7f1b, 0, 0 }, + { 15, 0x7f19, 0, 0 }, { 15, 0x7f17, 0, 0 }, + { 15, 0x7f15, 0, 0 }, { 15, 0x7f13, 0, 0 }, + { 15, 0x7f11, 0, 0 }, { 15, 0x7f0f, 0, 0 }, + { 15, 0x7f0d, 0, 0 }, { 15, 0x7f0b, 0, 0 }, + { 15, 0x7f09, 0, 0 }, { 15, 0x7f07, 0, 0 }, + { 15, 0x7f05, 0, 0 }, { 15, 0x7f03, 0, 0 }, + { 15, 0x7f01, 0, 0 }, { 16, 0xfe7f, 0, 0 }, + { 16, 0xfe7d, 0, 0 }, { 16, 0xfe7b, 0, 0 }, + { 16, 0xfe79, 0, 0 }, { 16, 0xfe77, 0, 0 }, + { 16, 0xfe75, 0, 0 }, { 16, 0xfe73, 0, 0 }, + { 16, 0xfe71, 0, 0 }, { 16, 0xfe6f, 0, 0 }, + { 16, 0xfe6d, 0, 0 }, { 16, 0xfe6b, 0, 0 }, + { 16, 0xfe69, 0, 0 }, { 16, 0xfe67, 0, 0 }, + { 16, 0xfe65, 0, 0 }, { 16, 0xfe63, 0, 0 }, + { 16, 0xfe61, 0, 0 }, { 16, 0xfe5f, 0, 0 }, + { 16, 0xfe5d, 0, 0 }, { 16, 0xfe5b, 0, 0 }, + { 16, 0xfe59, 0, 0 }, { 16, 0xfe57, 0, 0 }, + { 16, 0xfe55, 0, 0 }, { 16, 0xfe53, 0, 0 }, + { 16, 0xfe51, 0, 0 }, { 16, 0xfe4f, 0, 0 }, + { 16, 0xfe4d, 0, 0 }, { 16, 0xfe4b, 0, 0 }, + { 16, 0xfe49, 0, 0 }, { 16, 0xfe47, 0, 0 }, + { 16, 0xfe45, 0, 0 }, { 16, 0xfe43, 0, 0 }, + { 16, 0xfe41, 0, 0 }, { 27, 0x7fffff9, 7, 0x7f }, + { 27, 0x7fffff9, 7, 0x7d }, { 27, 0x7fffff9, 7, 0x7b }, + { 27, 0x7fffff9, 7, 0x79 }, { 27, 0x7fffff9, 7, 0x77 }, + { 27, 0x7fffff9, 7, 0x75 }, { 27, 0x7fffff9, 7, 0x73 }, + { 27, 0x7fffff9, 7, 0x71 }, { 27, 0x7fffff9, 7, 0x6f }, + { 27, 0x7fffff9, 7, 0x6d }, { 27, 0x7fffff9, 7, 0x6b }, + { 27, 0x7fffff9, 7, 0x69 }, { 27, 0x7fffff9, 7, 0x67 }, + { 27, 0x7fffff9, 7, 0x65 }, { 27, 0x7fffff9, 7, 0x63 }, + { 27, 0x7fffff9, 7, 0x61 }, { 27, 0x7fffff9, 7, 0x5f }, + { 27, 0x7fffff9, 7, 0x5d }, { 27, 0x7fffff9, 7, 0x5b }, + { 27, 0x7fffff9, 7, 0x59 }, { 27, 0x7fffff9, 7, 0x57 }, + { 27, 0x7fffff9, 7, 0x55 }, { 27, 0x7fffff9, 7, 0x53 }, + { 27, 0x7fffff9, 7, 0x51 }, { 27, 0x7fffff9, 7, 0x4f }, + { 27, 0x7fffff9, 7, 0x4d }, { 27, 0x7fffff9, 7, 0x4b }, + { 27, 0x7fffff9, 7, 0x49 }, { 27, 0x7fffff9, 7, 0x47 }, + { 27, 0x7fffff9, 7, 0x45 }, { 27, 0x7fffff9, 7, 0x43 }, + { 27, 0x7fffff9, 7, 0x41 }, { 27, 0x7fffff9, 7, 0x3f }, + { 27, 0x7fffff9, 7, 0x3d }, { 27, 0x7fffff9, 7, 0x3b }, + { 27, 0x7fffff9, 7, 0x39 }, { 27, 0x7fffff9, 7, 0x37 }, + { 27, 0x7fffff9, 7, 0x35 }, { 27, 0x7fffff9, 7, 0x33 }, + { 27, 0x7fffff9, 7, 0x31 }, { 27, 0x7fffff9, 7, 0x2f }, + { 27, 0x7fffff9, 7, 0x2d }, { 27, 0x7fffff9, 7, 0x2b }, + { 27, 0x7fffff9, 7, 0x29 }, { 27, 0x7fffff9, 7, 0x27 }, + { 27, 0x7fffff9, 7, 0x25 }, { 27, 0x7fffff9, 7, 0x23 }, + { 27, 0x7fffff9, 7, 0x21 }, { 27, 0x7fffff9, 7, 0x1f }, + { 27, 0x7fffff9, 7, 0x1d }, { 27, 0x7fffff9, 7, 0x1b }, + { 27, 0x7fffff9, 7, 0x19 }, { 27, 0x7fffff9, 7, 0x17 }, + { 27, 0x7fffff9, 7, 0x15 }, { 27, 0x7fffff9, 7, 0x13 }, + { 27, 0x7fffff9, 7, 0x11 }, { 27, 0x7fffff9, 7, 0xf }, + { 27, 0x7fffff9, 7, 0xd }, { 27, 0x7fffff9, 7, 0xb }, + { 27, 0x7fffff9, 7, 0x9 }, { 27, 0x7fffff9, 7, 0x7 }, + { 27, 0x7fffff9, 7, 0x5 }, { 27, 0x7fffff9, 7, 0x3 }, + { 27, 0x7fffff9, 7, 0x1 }, { 27, 0x7fffff9, 7, 0x1 } + }, + + /* + * prefixed with 2 zeroes + */ + { + { 6, 0x37, 0, 0 }, { 9, 0x1ef, 0, 0 }, + { 9, 0x1ed, 0, 0 }, { 12, 0xfd7, 0, 0 }, + { 12, 0xfd5, 0, 0 }, { 12, 0xfd3, 0, 0 }, + { 12, 0xfd1, 0, 0 }, { 13, 0x1fbf, 0, 0 }, + { 13, 0x1fbd, 0, 0 }, { 13, 0x1fbb, 0, 0 }, + { 13, 0x1fb9, 0, 0 }, { 13, 0x1fb7, 0, 0 }, + { 13, 0x1fb5, 0, 0 }, { 13, 0x1fb3, 0, 0 }, + { 13, 0x1fb1, 0, 0 }, { 25, 0x1ffff7f, 0, 0 }, + { 25, 0x1ffff7d, 0, 0 }, { 25, 0x1ffff7b, 0, 0 }, + { 25, 0x1ffff79, 0, 0 }, { 25, 0x1ffff77, 0, 0 }, + { 25, 0x1ffff75, 0, 0 }, { 25, 0x1ffff73, 0, 0 }, + { 25, 0x1ffff71, 0, 0 }, { 25, 0x1ffff6f, 0, 0 }, + { 25, 0x1ffff6d, 0, 0 }, { 25, 0x1ffff6b, 0, 0 }, + { 25, 0x1ffff69, 0, 0 }, { 25, 0x1ffff67, 0, 0 }, + { 25, 0x1ffff65, 0, 0 }, { 25, 0x1ffff63, 0, 0 }, + { 25, 0x1ffff61, 0, 0 }, { 30, 0x3ffffe3f, 0, 0 }, + { 30, 0x3ffffe3d, 0, 0 }, { 30, 0x3ffffe3b, 0, 0 }, + { 30, 0x3ffffe39, 0, 0 }, { 30, 0x3ffffe37, 0, 0 }, + { 30, 0x3ffffe35, 0, 0 }, { 30, 0x3ffffe33, 0, 0 }, + { 30, 0x3ffffe31, 0, 0 }, { 30, 0x3ffffe2f, 0, 0 }, + { 30, 0x3ffffe2d, 0, 0 }, { 30, 0x3ffffe2b, 0, 0 }, + { 30, 0x3ffffe29, 0, 0 }, { 30, 0x3ffffe27, 0, 0 }, + { 30, 0x3ffffe25, 0, 0 }, { 30, 0x3ffffe23, 0, 0 }, + { 30, 0x3ffffe21, 0, 0 }, { 30, 0x3ffffe1f, 0, 0 }, + { 30, 0x3ffffe1d, 0, 0 }, { 30, 0x3ffffe1b, 0, 0 }, + { 30, 0x3ffffe19, 0, 0 }, { 30, 0x3ffffe17, 0, 0 }, + { 30, 0x3ffffe15, 0, 0 }, { 30, 0x3ffffe13, 0, 0 }, + { 30, 0x3ffffe11, 0, 0 }, { 30, 0x3ffffe0f, 0, 0 }, + { 30, 0x3ffffe0d, 0, 0 }, { 30, 0x3ffffe0b, 0, 0 }, + { 30, 0x3ffffe09, 0, 0 }, { 30, 0x3ffffe07, 0, 0 }, + { 30, 0x3ffffe05, 0, 0 }, { 30, 0x3ffffe03, 0, 0 }, + { 30, 0x3ffffe01, 0, 0 }, { 27, 0x7fffffa, 7, 0x7f }, + { 27, 0x7fffffa, 7, 0x7d }, { 27, 0x7fffffa, 7, 0x7b }, + { 27, 0x7fffffa, 7, 0x79 }, { 27, 0x7fffffa, 7, 0x77 }, + { 27, 0x7fffffa, 7, 0x75 }, { 27, 0x7fffffa, 7, 0x73 }, + { 27, 0x7fffffa, 7, 0x71 }, { 27, 0x7fffffa, 7, 0x6f }, + { 27, 0x7fffffa, 7, 0x6d }, { 27, 0x7fffffa, 7, 0x6b }, + { 27, 0x7fffffa, 7, 0x69 }, { 27, 0x7fffffa, 7, 0x67 }, + { 27, 0x7fffffa, 7, 0x65 }, { 27, 0x7fffffa, 7, 0x63 }, + { 27, 0x7fffffa, 7, 0x61 }, { 27, 0x7fffffa, 7, 0x5f }, + { 27, 0x7fffffa, 7, 0x5d }, { 27, 0x7fffffa, 7, 0x5b }, + { 27, 0x7fffffa, 7, 0x59 }, { 27, 0x7fffffa, 7, 0x57 }, + { 27, 0x7fffffa, 7, 0x55 }, { 27, 0x7fffffa, 7, 0x53 }, + { 27, 0x7fffffa, 7, 0x51 }, { 27, 0x7fffffa, 7, 0x4f }, + { 27, 0x7fffffa, 7, 0x4d }, { 27, 0x7fffffa, 7, 0x4b }, + { 27, 0x7fffffa, 7, 0x49 }, { 27, 0x7fffffa, 7, 0x47 }, + { 27, 0x7fffffa, 7, 0x45 }, { 27, 0x7fffffa, 7, 0x43 }, + { 27, 0x7fffffa, 7, 0x41 }, { 27, 0x7fffffa, 7, 0x3f }, + { 27, 0x7fffffa, 7, 0x3d }, { 27, 0x7fffffa, 7, 0x3b }, + { 27, 0x7fffffa, 7, 0x39 }, { 27, 0x7fffffa, 7, 0x37 }, + { 27, 0x7fffffa, 7, 0x35 }, { 27, 0x7fffffa, 7, 0x33 }, + { 27, 0x7fffffa, 7, 0x31 }, { 27, 0x7fffffa, 7, 0x2f }, + { 27, 0x7fffffa, 7, 0x2d }, { 27, 0x7fffffa, 7, 0x2b }, + { 27, 0x7fffffa, 7, 0x29 }, { 27, 0x7fffffa, 7, 0x27 }, + { 27, 0x7fffffa, 7, 0x25 }, { 27, 0x7fffffa, 7, 0x23 }, + { 27, 0x7fffffa, 7, 0x21 }, { 27, 0x7fffffa, 7, 0x1f }, + { 27, 0x7fffffa, 7, 0x1d }, { 27, 0x7fffffa, 7, 0x1b }, + { 27, 0x7fffffa, 7, 0x19 }, { 27, 0x7fffffa, 7, 0x17 }, + { 27, 0x7fffffa, 7, 0x15 }, { 27, 0x7fffffa, 7, 0x13 }, + { 27, 0x7fffffa, 7, 0x11 }, { 27, 0x7fffffa, 7, 0xf }, + { 27, 0x7fffffa, 7, 0xd }, { 27, 0x7fffffa, 7, 0xb }, + { 27, 0x7fffffa, 7, 0x9 }, { 27, 0x7fffffa, 7, 0x7 }, + { 27, 0x7fffffa, 7, 0x5 }, { 27, 0x7fffffa, 7, 0x3 }, + { 27, 0x7fffffa, 7, 0x1 }, { 27, 0x7fffffa, 7, 0x1 } + }, + + /* + * prefixed with 3 zeroes + */ + { + { 7, 0x71, 0, 0 }, { 10, 0x3ef, 0, 0 }, + { 10, 0x3ed, 0, 0 }, { 17, 0x1ffdf, 0, 0 }, + { 17, 0x1ffdd, 0, 0 }, { 17, 0x1ffdb, 0, 0 }, + { 17, 0x1ffd9, 0, 0 }, { 21, 0x1fffbf, 0, 0 }, + { 21, 0x1fffbd, 0, 0 }, { 21, 0x1fffbb, 0, 0 }, + { 21, 0x1fffb9, 0, 0 }, { 21, 0x1fffb7, 0, 0 }, + { 21, 0x1fffb5, 0, 0 }, { 21, 0x1fffb3, 0, 0 }, + { 21, 0x1fffb1, 0, 0 }, { 26, 0x3ffff1f, 0, 0 }, + { 26, 0x3ffff1d, 0, 0 }, { 26, 0x3ffff1b, 0, 0 }, + { 26, 0x3ffff19, 0, 0 }, { 26, 0x3ffff17, 0, 0 }, + { 26, 0x3ffff15, 0, 0 }, { 26, 0x3ffff13, 0, 0 }, + { 26, 0x3ffff11, 0, 0 }, { 26, 0x3ffff0f, 0, 0 }, + { 26, 0x3ffff0d, 0, 0 }, { 26, 0x3ffff0b, 0, 0 }, + { 26, 0x3ffff09, 0, 0 }, { 26, 0x3ffff07, 0, 0 }, + { 26, 0x3ffff05, 0, 0 }, { 26, 0x3ffff03, 0, 0 }, + { 26, 0x3ffff01, 0, 0 }, { 30, 0x3ffffe7f, 0, 0 }, + { 30, 0x3ffffe7d, 0, 0 }, { 30, 0x3ffffe7b, 0, 0 }, + { 30, 0x3ffffe79, 0, 0 }, { 30, 0x3ffffe77, 0, 0 }, + { 30, 0x3ffffe75, 0, 0 }, { 30, 0x3ffffe73, 0, 0 }, + { 30, 0x3ffffe71, 0, 0 }, { 30, 0x3ffffe6f, 0, 0 }, + { 30, 0x3ffffe6d, 0, 0 }, { 30, 0x3ffffe6b, 0, 0 }, + { 30, 0x3ffffe69, 0, 0 }, { 30, 0x3ffffe67, 0, 0 }, + { 30, 0x3ffffe65, 0, 0 }, { 30, 0x3ffffe63, 0, 0 }, + { 30, 0x3ffffe61, 0, 0 }, { 30, 0x3ffffe5f, 0, 0 }, + { 30, 0x3ffffe5d, 0, 0 }, { 30, 0x3ffffe5b, 0, 0 }, + { 30, 0x3ffffe59, 0, 0 }, { 30, 0x3ffffe57, 0, 0 }, + { 30, 0x3ffffe55, 0, 0 }, { 30, 0x3ffffe53, 0, 0 }, + { 30, 0x3ffffe51, 0, 0 }, { 30, 0x3ffffe4f, 0, 0 }, + { 30, 0x3ffffe4d, 0, 0 }, { 30, 0x3ffffe4b, 0, 0 }, + { 30, 0x3ffffe49, 0, 0 }, { 30, 0x3ffffe47, 0, 0 }, + { 30, 0x3ffffe45, 0, 0 }, { 30, 0x3ffffe43, 0, 0 }, + { 30, 0x3ffffe41, 0, 0 }, { 27, 0x7fffffb, 7, 0x7f }, + { 27, 0x7fffffb, 7, 0x7d }, { 27, 0x7fffffb, 7, 0x7b }, + { 27, 0x7fffffb, 7, 0x79 }, { 27, 0x7fffffb, 7, 0x77 }, + { 27, 0x7fffffb, 7, 0x75 }, { 27, 0x7fffffb, 7, 0x73 }, + { 27, 0x7fffffb, 7, 0x71 }, { 27, 0x7fffffb, 7, 0x6f }, + { 27, 0x7fffffb, 7, 0x6d }, { 27, 0x7fffffb, 7, 0x6b }, + { 27, 0x7fffffb, 7, 0x69 }, { 27, 0x7fffffb, 7, 0x67 }, + { 27, 0x7fffffb, 7, 0x65 }, { 27, 0x7fffffb, 7, 0x63 }, + { 27, 0x7fffffb, 7, 0x61 }, { 27, 0x7fffffb, 7, 0x5f }, + { 27, 0x7fffffb, 7, 0x5d }, { 27, 0x7fffffb, 7, 0x5b }, + { 27, 0x7fffffb, 7, 0x59 }, { 27, 0x7fffffb, 7, 0x57 }, + { 27, 0x7fffffb, 7, 0x55 }, { 27, 0x7fffffb, 7, 0x53 }, + { 27, 0x7fffffb, 7, 0x51 }, { 27, 0x7fffffb, 7, 0x4f }, + { 27, 0x7fffffb, 7, 0x4d }, { 27, 0x7fffffb, 7, 0x4b }, + { 27, 0x7fffffb, 7, 0x49 }, { 27, 0x7fffffb, 7, 0x47 }, + { 27, 0x7fffffb, 7, 0x45 }, { 27, 0x7fffffb, 7, 0x43 }, + { 27, 0x7fffffb, 7, 0x41 }, { 27, 0x7fffffb, 7, 0x3f }, + { 27, 0x7fffffb, 7, 0x3d }, { 27, 0x7fffffb, 7, 0x3b }, + { 27, 0x7fffffb, 7, 0x39 }, { 27, 0x7fffffb, 7, 0x37 }, + { 27, 0x7fffffb, 7, 0x35 }, { 27, 0x7fffffb, 7, 0x33 }, + { 27, 0x7fffffb, 7, 0x31 }, { 27, 0x7fffffb, 7, 0x2f }, + { 27, 0x7fffffb, 7, 0x2d }, { 27, 0x7fffffb, 7, 0x2b }, + { 27, 0x7fffffb, 7, 0x29 }, { 27, 0x7fffffb, 7, 0x27 }, + { 27, 0x7fffffb, 7, 0x25 }, { 27, 0x7fffffb, 7, 0x23 }, + { 27, 0x7fffffb, 7, 0x21 }, { 27, 0x7fffffb, 7, 0x1f }, + { 27, 0x7fffffb, 7, 0x1d }, { 27, 0x7fffffb, 7, 0x1b }, + { 27, 0x7fffffb, 7, 0x19 }, { 27, 0x7fffffb, 7, 0x17 }, + { 27, 0x7fffffb, 7, 0x15 }, { 27, 0x7fffffb, 7, 0x13 }, + { 27, 0x7fffffb, 7, 0x11 }, { 27, 0x7fffffb, 7, 0xf }, + { 27, 0x7fffffb, 7, 0xd }, { 27, 0x7fffffb, 7, 0xb }, + { 27, 0x7fffffb, 7, 0x9 }, { 27, 0x7fffffb, 7, 0x7 }, + { 27, 0x7fffffb, 7, 0x5 }, { 27, 0x7fffffb, 7, 0x3 }, + { 27, 0x7fffffb, 7, 0x1 }, { 27, 0x7fffffb, 7, 0x1 } + }, + + /* + * prefixed with 4 zeroes + */ + { + { 8, 0xf1, 0, 0 }, { 11, 0x7e3, 0, 0 }, + { 11, 0x7e1, 0, 0 }, { 18, 0x3ffc7, 0, 0 }, + { 18, 0x3ffc5, 0, 0 }, { 18, 0x3ffc3, 0, 0 }, + { 18, 0x3ffc1, 0, 0 }, { 22, 0x3fff8f, 0, 0 }, + { 22, 0x3fff8d, 0, 0 }, { 22, 0x3fff8b, 0, 0 }, + { 22, 0x3fff89, 0, 0 }, { 22, 0x3fff87, 0, 0 }, + { 22, 0x3fff85, 0, 0 }, { 22, 0x3fff83, 0, 0 }, + { 22, 0x3fff81, 0, 0 }, { 26, 0x3ffff3f, 0, 0 }, + { 26, 0x3ffff3d, 0, 0 }, { 26, 0x3ffff3b, 0, 0 }, + { 26, 0x3ffff39, 0, 0 }, { 26, 0x3ffff37, 0, 0 }, + { 26, 0x3ffff35, 0, 0 }, { 26, 0x3ffff33, 0, 0 }, + { 26, 0x3ffff31, 0, 0 }, { 26, 0x3ffff2f, 0, 0 }, + { 26, 0x3ffff2d, 0, 0 }, { 26, 0x3ffff2b, 0, 0 }, + { 26, 0x3ffff29, 0, 0 }, { 26, 0x3ffff27, 0, 0 }, + { 26, 0x3ffff25, 0, 0 }, { 26, 0x3ffff23, 0, 0 }, + { 26, 0x3ffff21, 0, 0 }, { 30, 0x3ffffebf, 0, 0 }, + { 30, 0x3ffffebd, 0, 0 }, { 30, 0x3ffffebb, 0, 0 }, + { 30, 0x3ffffeb9, 0, 0 }, { 30, 0x3ffffeb7, 0, 0 }, + { 30, 0x3ffffeb5, 0, 0 }, { 30, 0x3ffffeb3, 0, 0 }, + { 30, 0x3ffffeb1, 0, 0 }, { 30, 0x3ffffeaf, 0, 0 }, + { 30, 0x3ffffead, 0, 0 }, { 30, 0x3ffffeab, 0, 0 }, + { 30, 0x3ffffea9, 0, 0 }, { 30, 0x3ffffea7, 0, 0 }, + { 30, 0x3ffffea5, 0, 0 }, { 30, 0x3ffffea3, 0, 0 }, + { 30, 0x3ffffea1, 0, 0 }, { 30, 0x3ffffe9f, 0, 0 }, + { 30, 0x3ffffe9d, 0, 0 }, { 30, 0x3ffffe9b, 0, 0 }, + { 30, 0x3ffffe99, 0, 0 }, { 30, 0x3ffffe97, 0, 0 }, + { 30, 0x3ffffe95, 0, 0 }, { 30, 0x3ffffe93, 0, 0 }, + { 30, 0x3ffffe91, 0, 0 }, { 30, 0x3ffffe8f, 0, 0 }, + { 30, 0x3ffffe8d, 0, 0 }, { 30, 0x3ffffe8b, 0, 0 }, + { 30, 0x3ffffe89, 0, 0 }, { 30, 0x3ffffe87, 0, 0 }, + { 30, 0x3ffffe85, 0, 0 }, { 30, 0x3ffffe83, 0, 0 }, + { 30, 0x3ffffe81, 0, 0 }, { 28, 0xffffff8, 7, 0x7f }, + { 28, 0xffffff8, 7, 0x7d }, { 28, 0xffffff8, 7, 0x7b }, + { 28, 0xffffff8, 7, 0x79 }, { 28, 0xffffff8, 7, 0x77 }, + { 28, 0xffffff8, 7, 0x75 }, { 28, 0xffffff8, 7, 0x73 }, + { 28, 0xffffff8, 7, 0x71 }, { 28, 0xffffff8, 7, 0x6f }, + { 28, 0xffffff8, 7, 0x6d }, { 28, 0xffffff8, 7, 0x6b }, + { 28, 0xffffff8, 7, 0x69 }, { 28, 0xffffff8, 7, 0x67 }, + { 28, 0xffffff8, 7, 0x65 }, { 28, 0xffffff8, 7, 0x63 }, + { 28, 0xffffff8, 7, 0x61 }, { 28, 0xffffff8, 7, 0x5f }, + { 28, 0xffffff8, 7, 0x5d }, { 28, 0xffffff8, 7, 0x5b }, + { 28, 0xffffff8, 7, 0x59 }, { 28, 0xffffff8, 7, 0x57 }, + { 28, 0xffffff8, 7, 0x55 }, { 28, 0xffffff8, 7, 0x53 }, + { 28, 0xffffff8, 7, 0x51 }, { 28, 0xffffff8, 7, 0x4f }, + { 28, 0xffffff8, 7, 0x4d }, { 28, 0xffffff8, 7, 0x4b }, + { 28, 0xffffff8, 7, 0x49 }, { 28, 0xffffff8, 7, 0x47 }, + { 28, 0xffffff8, 7, 0x45 }, { 28, 0xffffff8, 7, 0x43 }, + { 28, 0xffffff8, 7, 0x41 }, { 28, 0xffffff8, 7, 0x3f }, + { 28, 0xffffff8, 7, 0x3d }, { 28, 0xffffff8, 7, 0x3b }, + { 28, 0xffffff8, 7, 0x39 }, { 28, 0xffffff8, 7, 0x37 }, + { 28, 0xffffff8, 7, 0x35 }, { 28, 0xffffff8, 7, 0x33 }, + { 28, 0xffffff8, 7, 0x31 }, { 28, 0xffffff8, 7, 0x2f }, + { 28, 0xffffff8, 7, 0x2d }, { 28, 0xffffff8, 7, 0x2b }, + { 28, 0xffffff8, 7, 0x29 }, { 28, 0xffffff8, 7, 0x27 }, + { 28, 0xffffff8, 7, 0x25 }, { 28, 0xffffff8, 7, 0x23 }, + { 28, 0xffffff8, 7, 0x21 }, { 28, 0xffffff8, 7, 0x1f }, + { 28, 0xffffff8, 7, 0x1d }, { 28, 0xffffff8, 7, 0x1b }, + { 28, 0xffffff8, 7, 0x19 }, { 28, 0xffffff8, 7, 0x17 }, + { 28, 0xffffff8, 7, 0x15 }, { 28, 0xffffff8, 7, 0x13 }, + { 28, 0xffffff8, 7, 0x11 }, { 28, 0xffffff8, 7, 0xf }, + { 28, 0xffffff8, 7, 0xd }, { 28, 0xffffff8, 7, 0xb }, + { 28, 0xffffff8, 7, 0x9 }, { 28, 0xffffff8, 7, 0x7 }, + { 28, 0xffffff8, 7, 0x5 }, { 28, 0xffffff8, 7, 0x3 }, + { 28, 0xffffff8, 7, 0x1 }, { 0, 0, 0, 0 } + }, + + /* + * prefixed with 5 zeroes + */ + { + { 8, 0xf3, 0, 0 }, { 11, 0x7e7, 0, 0 }, + { 11, 0x7e5, 0, 0 }, { 18, 0x3ffcf, 0, 0 }, + { 18, 0x3ffcd, 0, 0 }, { 18, 0x3ffcb, 0, 0 }, + { 18, 0x3ffc9, 0, 0 }, { 22, 0x3fff9f, 0, 0 }, + { 22, 0x3fff9d, 0, 0 }, { 22, 0x3fff9b, 0, 0 }, + { 22, 0x3fff99, 0, 0 }, { 22, 0x3fff97, 0, 0 }, + { 22, 0x3fff95, 0, 0 }, { 22, 0x3fff93, 0, 0 }, + { 22, 0x3fff91, 0, 0 }, { 26, 0x3ffff5f, 0, 0 }, + { 26, 0x3ffff5d, 0, 0 }, { 26, 0x3ffff5b, 0, 0 }, + { 26, 0x3ffff59, 0, 0 }, { 26, 0x3ffff57, 0, 0 }, + { 26, 0x3ffff55, 0, 0 }, { 26, 0x3ffff53, 0, 0 }, + { 26, 0x3ffff51, 0, 0 }, { 26, 0x3ffff4f, 0, 0 }, + { 26, 0x3ffff4d, 0, 0 }, { 26, 0x3ffff4b, 0, 0 }, + { 26, 0x3ffff49, 0, 0 }, { 26, 0x3ffff47, 0, 0 }, + { 26, 0x3ffff45, 0, 0 }, { 26, 0x3ffff43, 0, 0 }, + { 26, 0x3ffff41, 0, 0 }, { 30, 0x3ffffeff, 0, 0 }, + { 30, 0x3ffffefd, 0, 0 }, { 30, 0x3ffffefb, 0, 0 }, + { 30, 0x3ffffef9, 0, 0 }, { 30, 0x3ffffef7, 0, 0 }, + { 30, 0x3ffffef5, 0, 0 }, { 30, 0x3ffffef3, 0, 0 }, + { 30, 0x3ffffef1, 0, 0 }, { 30, 0x3ffffeef, 0, 0 }, + { 30, 0x3ffffeed, 0, 0 }, { 30, 0x3ffffeeb, 0, 0 }, + { 30, 0x3ffffee9, 0, 0 }, { 30, 0x3ffffee7, 0, 0 }, + { 30, 0x3ffffee5, 0, 0 }, { 30, 0x3ffffee3, 0, 0 }, + { 30, 0x3ffffee1, 0, 0 }, { 30, 0x3ffffedf, 0, 0 }, + { 30, 0x3ffffedd, 0, 0 }, { 30, 0x3ffffedb, 0, 0 }, + { 30, 0x3ffffed9, 0, 0 }, { 30, 0x3ffffed7, 0, 0 }, + { 30, 0x3ffffed5, 0, 0 }, { 30, 0x3ffffed3, 0, 0 }, + { 30, 0x3ffffed1, 0, 0 }, { 30, 0x3ffffecf, 0, 0 }, + { 30, 0x3ffffecd, 0, 0 }, { 30, 0x3ffffecb, 0, 0 }, + { 30, 0x3ffffec9, 0, 0 }, { 30, 0x3ffffec7, 0, 0 }, + { 30, 0x3ffffec5, 0, 0 }, { 30, 0x3ffffec3, 0, 0 }, + { 30, 0x3ffffec1, 0, 0 }, { 28, 0xffffff9, 7, 0x7f }, + { 28, 0xffffff9, 7, 0x7d }, { 28, 0xffffff9, 7, 0x7b }, + { 28, 0xffffff9, 7, 0x79 }, { 28, 0xffffff9, 7, 0x77 }, + { 28, 0xffffff9, 7, 0x75 }, { 28, 0xffffff9, 7, 0x73 }, + { 28, 0xffffff9, 7, 0x71 }, { 28, 0xffffff9, 7, 0x6f }, + { 28, 0xffffff9, 7, 0x6d }, { 28, 0xffffff9, 7, 0x6b }, + { 28, 0xffffff9, 7, 0x69 }, { 28, 0xffffff9, 7, 0x67 }, + { 28, 0xffffff9, 7, 0x65 }, { 28, 0xffffff9, 7, 0x63 }, + { 28, 0xffffff9, 7, 0x61 }, { 28, 0xffffff9, 7, 0x5f }, + { 28, 0xffffff9, 7, 0x5d }, { 28, 0xffffff9, 7, 0x5b }, + { 28, 0xffffff9, 7, 0x59 }, { 28, 0xffffff9, 7, 0x57 }, + { 28, 0xffffff9, 7, 0x55 }, { 28, 0xffffff9, 7, 0x53 }, + { 28, 0xffffff9, 7, 0x51 }, { 28, 0xffffff9, 7, 0x4f }, + { 28, 0xffffff9, 7, 0x4d }, { 28, 0xffffff9, 7, 0x4b }, + { 28, 0xffffff9, 7, 0x49 }, { 28, 0xffffff9, 7, 0x47 }, + { 28, 0xffffff9, 7, 0x45 }, { 28, 0xffffff9, 7, 0x43 }, + { 28, 0xffffff9, 7, 0x41 }, { 28, 0xffffff9, 7, 0x3f }, + { 28, 0xffffff9, 7, 0x3d }, { 28, 0xffffff9, 7, 0x3b }, + { 28, 0xffffff9, 7, 0x39 }, { 28, 0xffffff9, 7, 0x37 }, + { 28, 0xffffff9, 7, 0x35 }, { 28, 0xffffff9, 7, 0x33 }, + { 28, 0xffffff9, 7, 0x31 }, { 28, 0xffffff9, 7, 0x2f }, + { 28, 0xffffff9, 7, 0x2d }, { 28, 0xffffff9, 7, 0x2b }, + { 28, 0xffffff9, 7, 0x29 }, { 28, 0xffffff9, 7, 0x27 }, + { 28, 0xffffff9, 7, 0x25 }, { 28, 0xffffff9, 7, 0x23 }, + { 28, 0xffffff9, 7, 0x21 }, { 28, 0xffffff9, 7, 0x1f }, + { 28, 0xffffff9, 7, 0x1d }, { 28, 0xffffff9, 7, 0x1b }, + { 28, 0xffffff9, 7, 0x19 }, { 28, 0xffffff9, 7, 0x17 }, + { 28, 0xffffff9, 7, 0x15 }, { 28, 0xffffff9, 7, 0x13 }, + { 28, 0xffffff9, 7, 0x11 }, { 28, 0xffffff9, 7, 0xf }, + { 28, 0xffffff9, 7, 0xd }, { 28, 0xffffff9, 7, 0xb }, + { 28, 0xffffff9, 7, 0x9 }, { 28, 0xffffff9, 7, 0x7 }, + { 28, 0xffffff9, 7, 0x5 }, { 28, 0xffffff9, 7, 0x3 }, + { 28, 0xffffff9, 7, 0x1 }, { 0, 0, 0, 0 } + }, + + /* + * prefixed with 6 zeroes + */ + { + { 8, 0xf5, 0, 0 }, { 14, 0x3feb, 0, 0 }, + { 14, 0x3fe9, 0, 0 }, { 18, 0x3ffd7, 0, 0 }, + { 18, 0x3ffd5, 0, 0 }, { 18, 0x3ffd3, 0, 0 }, + { 18, 0x3ffd1, 0, 0 }, { 22, 0x3fffaf, 0, 0 }, + { 22, 0x3fffad, 0, 0 }, { 22, 0x3fffab, 0, 0 }, + { 22, 0x3fffa9, 0, 0 }, { 22, 0x3fffa7, 0, 0 }, + { 22, 0x3fffa5, 0, 0 }, { 22, 0x3fffa3, 0, 0 }, + { 22, 0x3fffa1, 0, 0 }, { 26, 0x3ffff7f, 0, 0 }, + { 26, 0x3ffff7d, 0, 0 }, { 26, 0x3ffff7b, 0, 0 }, + { 26, 0x3ffff79, 0, 0 }, { 26, 0x3ffff77, 0, 0 }, + { 26, 0x3ffff75, 0, 0 }, { 26, 0x3ffff73, 0, 0 }, + { 26, 0x3ffff71, 0, 0 }, { 26, 0x3ffff6f, 0, 0 }, + { 26, 0x3ffff6d, 0, 0 }, { 26, 0x3ffff6b, 0, 0 }, + { 26, 0x3ffff69, 0, 0 }, { 26, 0x3ffff67, 0, 0 }, + { 26, 0x3ffff65, 0, 0 }, { 26, 0x3ffff63, 0, 0 }, + { 26, 0x3ffff61, 0, 0 }, { 31, 0x7ffffe3f, 0, 0 }, + { 31, 0x7ffffe3d, 0, 0 }, { 31, 0x7ffffe3b, 0, 0 }, + { 31, 0x7ffffe39, 0, 0 }, { 31, 0x7ffffe37, 0, 0 }, + { 31, 0x7ffffe35, 0, 0 }, { 31, 0x7ffffe33, 0, 0 }, + { 31, 0x7ffffe31, 0, 0 }, { 31, 0x7ffffe2f, 0, 0 }, + { 31, 0x7ffffe2d, 0, 0 }, { 31, 0x7ffffe2b, 0, 0 }, + { 31, 0x7ffffe29, 0, 0 }, { 31, 0x7ffffe27, 0, 0 }, + { 31, 0x7ffffe25, 0, 0 }, { 31, 0x7ffffe23, 0, 0 }, + { 31, 0x7ffffe21, 0, 0 }, { 31, 0x7ffffe1f, 0, 0 }, + { 31, 0x7ffffe1d, 0, 0 }, { 31, 0x7ffffe1b, 0, 0 }, + { 31, 0x7ffffe19, 0, 0 }, { 31, 0x7ffffe17, 0, 0 }, + { 31, 0x7ffffe15, 0, 0 }, { 31, 0x7ffffe13, 0, 0 }, + { 31, 0x7ffffe11, 0, 0 }, { 31, 0x7ffffe0f, 0, 0 }, + { 31, 0x7ffffe0d, 0, 0 }, { 31, 0x7ffffe0b, 0, 0 }, + { 31, 0x7ffffe09, 0, 0 }, { 31, 0x7ffffe07, 0, 0 }, + { 31, 0x7ffffe05, 0, 0 }, { 31, 0x7ffffe03, 0, 0 }, + { 31, 0x7ffffe01, 0, 0 }, { 28, 0xffffffa, 7, 0x7f }, + { 28, 0xffffffa, 7, 0x7d }, { 28, 0xffffffa, 7, 0x7b }, + { 28, 0xffffffa, 7, 0x79 }, { 28, 0xffffffa, 7, 0x77 }, + { 28, 0xffffffa, 7, 0x75 }, { 28, 0xffffffa, 7, 0x73 }, + { 28, 0xffffffa, 7, 0x71 }, { 28, 0xffffffa, 7, 0x6f }, + { 28, 0xffffffa, 7, 0x6d }, { 28, 0xffffffa, 7, 0x6b }, + { 28, 0xffffffa, 7, 0x69 }, { 28, 0xffffffa, 7, 0x67 }, + { 28, 0xffffffa, 7, 0x65 }, { 28, 0xffffffa, 7, 0x63 }, + { 28, 0xffffffa, 7, 0x61 }, { 28, 0xffffffa, 7, 0x5f }, + { 28, 0xffffffa, 7, 0x5d }, { 28, 0xffffffa, 7, 0x5b }, + { 28, 0xffffffa, 7, 0x59 }, { 28, 0xffffffa, 7, 0x57 }, + { 28, 0xffffffa, 7, 0x55 }, { 28, 0xffffffa, 7, 0x53 }, + { 28, 0xffffffa, 7, 0x51 }, { 28, 0xffffffa, 7, 0x4f }, + { 28, 0xffffffa, 7, 0x4d }, { 28, 0xffffffa, 7, 0x4b }, + { 28, 0xffffffa, 7, 0x49 }, { 28, 0xffffffa, 7, 0x47 }, + { 28, 0xffffffa, 7, 0x45 }, { 28, 0xffffffa, 7, 0x43 }, + { 28, 0xffffffa, 7, 0x41 }, { 28, 0xffffffa, 7, 0x3f }, + { 28, 0xffffffa, 7, 0x3d }, { 28, 0xffffffa, 7, 0x3b }, + { 28, 0xffffffa, 7, 0x39 }, { 28, 0xffffffa, 7, 0x37 }, + { 28, 0xffffffa, 7, 0x35 }, { 28, 0xffffffa, 7, 0x33 }, + { 28, 0xffffffa, 7, 0x31 }, { 28, 0xffffffa, 7, 0x2f }, + { 28, 0xffffffa, 7, 0x2d }, { 28, 0xffffffa, 7, 0x2b }, + { 28, 0xffffffa, 7, 0x29 }, { 28, 0xffffffa, 7, 0x27 }, + { 28, 0xffffffa, 7, 0x25 }, { 28, 0xffffffa, 7, 0x23 }, + { 28, 0xffffffa, 7, 0x21 }, { 28, 0xffffffa, 7, 0x1f }, + { 28, 0xffffffa, 7, 0x1d }, { 28, 0xffffffa, 7, 0x1b }, + { 28, 0xffffffa, 7, 0x19 }, { 28, 0xffffffa, 7, 0x17 }, + { 28, 0xffffffa, 7, 0x15 }, { 28, 0xffffffa, 7, 0x13 }, + { 28, 0xffffffa, 7, 0x11 }, { 28, 0xffffffa, 7, 0xf }, + { 28, 0xffffffa, 7, 0xd }, { 28, 0xffffffa, 7, 0xb }, + { 28, 0xffffffa, 7, 0x9 }, { 28, 0xffffffa, 7, 0x7 }, + { 28, 0xffffffa, 7, 0x5 }, { 28, 0xffffffa, 7, 0x3 }, + { 28, 0xffffffa, 7, 0x1 }, { 0, 0, 0, 0 } + }, + + /* + * prefixed with 7 zeroes + */ + { + { 9, 0x1f3, 0, 0 }, { 14, 0x3fef, 0, 0 }, + { 14, 0x3fed, 0, 0 }, { 18, 0x3ffdf, 0, 0 }, + { 18, 0x3ffdd, 0, 0 }, { 18, 0x3ffdb, 0, 0 }, + { 18, 0x3ffd9, 0, 0 }, { 22, 0x3fffbf, 0, 0 }, + { 22, 0x3fffbd, 0, 0 }, { 22, 0x3fffbb, 0, 0 }, + { 22, 0x3fffb9, 0, 0 }, { 22, 0x3fffb7, 0, 0 }, + { 22, 0x3fffb5, 0, 0 }, { 22, 0x3fffb3, 0, 0 }, + { 22, 0x3fffb1, 0, 0 }, { 27, 0x7ffff1f, 0, 0 }, + { 27, 0x7ffff1d, 0, 0 }, { 27, 0x7ffff1b, 0, 0 }, + { 27, 0x7ffff19, 0, 0 }, { 27, 0x7ffff17, 0, 0 }, + { 27, 0x7ffff15, 0, 0 }, { 27, 0x7ffff13, 0, 0 }, + { 27, 0x7ffff11, 0, 0 }, { 27, 0x7ffff0f, 0, 0 }, + { 27, 0x7ffff0d, 0, 0 }, { 27, 0x7ffff0b, 0, 0 }, + { 27, 0x7ffff09, 0, 0 }, { 27, 0x7ffff07, 0, 0 }, + { 27, 0x7ffff05, 0, 0 }, { 27, 0x7ffff03, 0, 0 }, + { 27, 0x7ffff01, 0, 0 }, { 31, 0x7ffffe7f, 0, 0 }, + { 31, 0x7ffffe7d, 0, 0 }, { 31, 0x7ffffe7b, 0, 0 }, + { 31, 0x7ffffe79, 0, 0 }, { 31, 0x7ffffe77, 0, 0 }, + { 31, 0x7ffffe75, 0, 0 }, { 31, 0x7ffffe73, 0, 0 }, + { 31, 0x7ffffe71, 0, 0 }, { 31, 0x7ffffe6f, 0, 0 }, + { 31, 0x7ffffe6d, 0, 0 }, { 31, 0x7ffffe6b, 0, 0 }, + { 31, 0x7ffffe69, 0, 0 }, { 31, 0x7ffffe67, 0, 0 }, + { 31, 0x7ffffe65, 0, 0 }, { 31, 0x7ffffe63, 0, 0 }, + { 31, 0x7ffffe61, 0, 0 }, { 31, 0x7ffffe5f, 0, 0 }, + { 31, 0x7ffffe5d, 0, 0 }, { 31, 0x7ffffe5b, 0, 0 }, + { 31, 0x7ffffe59, 0, 0 }, { 31, 0x7ffffe57, 0, 0 }, + { 31, 0x7ffffe55, 0, 0 }, { 31, 0x7ffffe53, 0, 0 }, + { 31, 0x7ffffe51, 0, 0 }, { 31, 0x7ffffe4f, 0, 0 }, + { 31, 0x7ffffe4d, 0, 0 }, { 31, 0x7ffffe4b, 0, 0 }, + { 31, 0x7ffffe49, 0, 0 }, { 31, 0x7ffffe47, 0, 0 }, + { 31, 0x7ffffe45, 0, 0 }, { 31, 0x7ffffe43, 0, 0 }, + { 31, 0x7ffffe41, 0, 0 }, { 28, 0xffffffb, 7, 0x7f }, + { 28, 0xffffffb, 7, 0x7d }, { 28, 0xffffffb, 7, 0x7b }, + { 28, 0xffffffb, 7, 0x79 }, { 28, 0xffffffb, 7, 0x77 }, + { 28, 0xffffffb, 7, 0x75 }, { 28, 0xffffffb, 7, 0x73 }, + { 28, 0xffffffb, 7, 0x71 }, { 28, 0xffffffb, 7, 0x6f }, + { 28, 0xffffffb, 7, 0x6d }, { 28, 0xffffffb, 7, 0x6b }, + { 28, 0xffffffb, 7, 0x69 }, { 28, 0xffffffb, 7, 0x67 }, + { 28, 0xffffffb, 7, 0x65 }, { 28, 0xffffffb, 7, 0x63 }, + { 28, 0xffffffb, 7, 0x61 }, { 28, 0xffffffb, 7, 0x5f }, + { 28, 0xffffffb, 7, 0x5d }, { 28, 0xffffffb, 7, 0x5b }, + { 28, 0xffffffb, 7, 0x59 }, { 28, 0xffffffb, 7, 0x57 }, + { 28, 0xffffffb, 7, 0x55 }, { 28, 0xffffffb, 7, 0x53 }, + { 28, 0xffffffb, 7, 0x51 }, { 28, 0xffffffb, 7, 0x4f }, + { 28, 0xffffffb, 7, 0x4d }, { 28, 0xffffffb, 7, 0x4b }, + { 28, 0xffffffb, 7, 0x49 }, { 28, 0xffffffb, 7, 0x47 }, + { 28, 0xffffffb, 7, 0x45 }, { 28, 0xffffffb, 7, 0x43 }, + { 28, 0xffffffb, 7, 0x41 }, { 28, 0xffffffb, 7, 0x3f }, + { 28, 0xffffffb, 7, 0x3d }, { 28, 0xffffffb, 7, 0x3b }, + { 28, 0xffffffb, 7, 0x39 }, { 28, 0xffffffb, 7, 0x37 }, + { 28, 0xffffffb, 7, 0x35 }, { 28, 0xffffffb, 7, 0x33 }, + { 28, 0xffffffb, 7, 0x31 }, { 28, 0xffffffb, 7, 0x2f }, + { 28, 0xffffffb, 7, 0x2d }, { 28, 0xffffffb, 7, 0x2b }, + { 28, 0xffffffb, 7, 0x29 }, { 28, 0xffffffb, 7, 0x27 }, + { 28, 0xffffffb, 7, 0x25 }, { 28, 0xffffffb, 7, 0x23 }, + { 28, 0xffffffb, 7, 0x21 }, { 28, 0xffffffb, 7, 0x1f }, + { 28, 0xffffffb, 7, 0x1d }, { 28, 0xffffffb, 7, 0x1b }, + { 28, 0xffffffb, 7, 0x19 }, { 28, 0xffffffb, 7, 0x17 }, + { 28, 0xffffffb, 7, 0x15 }, { 28, 0xffffffb, 7, 0x13 }, + { 28, 0xffffffb, 7, 0x11 }, { 28, 0xffffffb, 7, 0xf }, + { 28, 0xffffffb, 7, 0xd }, { 28, 0xffffffb, 7, 0xb }, + { 28, 0xffffffb, 7, 0x9 }, { 28, 0xffffffb, 7, 0x7 }, + { 28, 0xffffffb, 7, 0x5 }, { 28, 0xffffffb, 7, 0x3 }, + { 28, 0xffffffb, 7, 0x1 }, { 0, 0, 0, 0 } + }, + + /* + * prefixed with 8 zeroes + */ + { + { 9, 0x1f5, 0, 0 }, { 15, 0x7fe3, 0, 0 }, + { 15, 0x7fe1, 0, 0 }, { 19, 0x7ffc7, 0, 0 }, + { 19, 0x7ffc5, 0, 0 }, { 19, 0x7ffc3, 0, 0 }, + { 19, 0x7ffc1, 0, 0 }, { 23, 0x7fff8f, 0, 0 }, + { 23, 0x7fff8d, 0, 0 }, { 23, 0x7fff8b, 0, 0 }, + { 23, 0x7fff89, 0, 0 }, { 23, 0x7fff87, 0, 0 }, + { 23, 0x7fff85, 0, 0 }, { 23, 0x7fff83, 0, 0 }, + { 23, 0x7fff81, 0, 0 }, { 27, 0x7ffff3f, 0, 0 }, + { 27, 0x7ffff3d, 0, 0 }, { 27, 0x7ffff3b, 0, 0 }, + { 27, 0x7ffff39, 0, 0 }, { 27, 0x7ffff37, 0, 0 }, + { 27, 0x7ffff35, 0, 0 }, { 27, 0x7ffff33, 0, 0 }, + { 27, 0x7ffff31, 0, 0 }, { 27, 0x7ffff2f, 0, 0 }, + { 27, 0x7ffff2d, 0, 0 }, { 27, 0x7ffff2b, 0, 0 }, + { 27, 0x7ffff29, 0, 0 }, { 27, 0x7ffff27, 0, 0 }, + { 27, 0x7ffff25, 0, 0 }, { 27, 0x7ffff23, 0, 0 }, + { 27, 0x7ffff21, 0, 0 }, { 31, 0x7ffffebf, 0, 0 }, + { 31, 0x7ffffebd, 0, 0 }, { 31, 0x7ffffebb, 0, 0 }, + { 31, 0x7ffffeb9, 0, 0 }, { 31, 0x7ffffeb7, 0, 0 }, + { 31, 0x7ffffeb5, 0, 0 }, { 31, 0x7ffffeb3, 0, 0 }, + { 31, 0x7ffffeb1, 0, 0 }, { 31, 0x7ffffeaf, 0, 0 }, + { 31, 0x7ffffead, 0, 0 }, { 31, 0x7ffffeab, 0, 0 }, + { 31, 0x7ffffea9, 0, 0 }, { 31, 0x7ffffea7, 0, 0 }, + { 31, 0x7ffffea5, 0, 0 }, { 31, 0x7ffffea3, 0, 0 }, + { 31, 0x7ffffea1, 0, 0 }, { 31, 0x7ffffe9f, 0, 0 }, + { 31, 0x7ffffe9d, 0, 0 }, { 31, 0x7ffffe9b, 0, 0 }, + { 31, 0x7ffffe99, 0, 0 }, { 31, 0x7ffffe97, 0, 0 }, + { 31, 0x7ffffe95, 0, 0 }, { 31, 0x7ffffe93, 0, 0 }, + { 31, 0x7ffffe91, 0, 0 }, { 31, 0x7ffffe8f, 0, 0 }, + { 31, 0x7ffffe8d, 0, 0 }, { 31, 0x7ffffe8b, 0, 0 }, + { 31, 0x7ffffe89, 0, 0 }, { 31, 0x7ffffe87, 0, 0 }, + { 31, 0x7ffffe85, 0, 0 }, { 31, 0x7ffffe83, 0, 0 }, + { 31, 0x7ffffe81, 0, 0 }, { 29, 0x1ffffff8, 7, 0x7f }, + { 29, 0x1ffffff8, 7, 0x7d }, { 29, 0x1ffffff8, 7, 0x7b }, + { 29, 0x1ffffff8, 7, 0x79 }, { 29, 0x1ffffff8, 7, 0x77 }, + { 29, 0x1ffffff8, 7, 0x75 }, { 29, 0x1ffffff8, 7, 0x73 }, + { 29, 0x1ffffff8, 7, 0x71 }, { 29, 0x1ffffff8, 7, 0x6f }, + { 29, 0x1ffffff8, 7, 0x6d }, { 29, 0x1ffffff8, 7, 0x6b }, + { 29, 0x1ffffff8, 7, 0x69 }, { 29, 0x1ffffff8, 7, 0x67 }, + { 29, 0x1ffffff8, 7, 0x65 }, { 29, 0x1ffffff8, 7, 0x63 }, + { 29, 0x1ffffff8, 7, 0x61 }, { 29, 0x1ffffff8, 7, 0x5f }, + { 29, 0x1ffffff8, 7, 0x5d }, { 29, 0x1ffffff8, 7, 0x5b }, + { 29, 0x1ffffff8, 7, 0x59 }, { 29, 0x1ffffff8, 7, 0x57 }, + { 29, 0x1ffffff8, 7, 0x55 }, { 29, 0x1ffffff8, 7, 0x53 }, + { 29, 0x1ffffff8, 7, 0x51 }, { 29, 0x1ffffff8, 7, 0x4f }, + { 29, 0x1ffffff8, 7, 0x4d }, { 29, 0x1ffffff8, 7, 0x4b }, + { 29, 0x1ffffff8, 7, 0x49 }, { 29, 0x1ffffff8, 7, 0x47 }, + { 29, 0x1ffffff8, 7, 0x45 }, { 29, 0x1ffffff8, 7, 0x43 }, + { 29, 0x1ffffff8, 7, 0x41 }, { 29, 0x1ffffff8, 7, 0x3f }, + { 29, 0x1ffffff8, 7, 0x3d }, { 29, 0x1ffffff8, 7, 0x3b }, + { 29, 0x1ffffff8, 7, 0x39 }, { 29, 0x1ffffff8, 7, 0x37 }, + { 29, 0x1ffffff8, 7, 0x35 }, { 29, 0x1ffffff8, 7, 0x33 }, + { 29, 0x1ffffff8, 7, 0x31 }, { 29, 0x1ffffff8, 7, 0x2f }, + { 29, 0x1ffffff8, 7, 0x2d }, { 29, 0x1ffffff8, 7, 0x2b }, + { 29, 0x1ffffff8, 7, 0x29 }, { 29, 0x1ffffff8, 7, 0x27 }, + { 29, 0x1ffffff8, 7, 0x25 }, { 29, 0x1ffffff8, 7, 0x23 }, + { 29, 0x1ffffff8, 7, 0x21 }, { 29, 0x1ffffff8, 7, 0x1f }, + { 29, 0x1ffffff8, 7, 0x1d }, { 29, 0x1ffffff8, 7, 0x1b }, + { 29, 0x1ffffff8, 7, 0x19 }, { 29, 0x1ffffff8, 7, 0x17 }, + { 29, 0x1ffffff8, 7, 0x15 }, { 29, 0x1ffffff8, 7, 0x13 }, + { 29, 0x1ffffff8, 7, 0x11 }, { 29, 0x1ffffff8, 7, 0xf }, + { 29, 0x1ffffff8, 7, 0xd }, { 29, 0x1ffffff8, 7, 0xb }, + { 29, 0x1ffffff8, 7, 0x9 }, { 29, 0x1ffffff8, 7, 0x7 }, + { 29, 0x1ffffff8, 7, 0x5 }, { 29, 0x1ffffff8, 7, 0x3 }, + { 29, 0x1ffffff8, 7, 0x1 }, { 0, 0, 0, 0 } + }, + + /* + * prefixed with 9 zeroes + */ + { + { 11, 0x7f7, 0, 0 }, { 15, 0x7fe7, 0, 0 }, + { 15, 0x7fe5, 0, 0 }, { 19, 0x7ffcf, 0, 0 }, + { 19, 0x7ffcd, 0, 0 }, { 19, 0x7ffcb, 0, 0 }, + { 19, 0x7ffc9, 0, 0 }, { 23, 0x7fff9f, 0, 0 }, + { 23, 0x7fff9d, 0, 0 }, { 23, 0x7fff9b, 0, 0 }, + { 23, 0x7fff99, 0, 0 }, { 23, 0x7fff97, 0, 0 }, + { 23, 0x7fff95, 0, 0 }, { 23, 0x7fff93, 0, 0 }, + { 23, 0x7fff91, 0, 0 }, { 27, 0x7ffff5f, 0, 0 }, + { 27, 0x7ffff5d, 0, 0 }, { 27, 0x7ffff5b, 0, 0 }, + { 27, 0x7ffff59, 0, 0 }, { 27, 0x7ffff57, 0, 0 }, + { 27, 0x7ffff55, 0, 0 }, { 27, 0x7ffff53, 0, 0 }, + { 27, 0x7ffff51, 0, 0 }, { 27, 0x7ffff4f, 0, 0 }, + { 27, 0x7ffff4d, 0, 0 }, { 27, 0x7ffff4b, 0, 0 }, + { 27, 0x7ffff49, 0, 0 }, { 27, 0x7ffff47, 0, 0 }, + { 27, 0x7ffff45, 0, 0 }, { 27, 0x7ffff43, 0, 0 }, + { 27, 0x7ffff41, 0, 0 }, { 31, 0x7ffffeff, 0, 0 }, + { 31, 0x7ffffefd, 0, 0 }, { 31, 0x7ffffefb, 0, 0 }, + { 31, 0x7ffffef9, 0, 0 }, { 31, 0x7ffffef7, 0, 0 }, + { 31, 0x7ffffef5, 0, 0 }, { 31, 0x7ffffef3, 0, 0 }, + { 31, 0x7ffffef1, 0, 0 }, { 31, 0x7ffffeef, 0, 0 }, + { 31, 0x7ffffeed, 0, 0 }, { 31, 0x7ffffeeb, 0, 0 }, + { 31, 0x7ffffee9, 0, 0 }, { 31, 0x7ffffee7, 0, 0 }, + { 31, 0x7ffffee5, 0, 0 }, { 31, 0x7ffffee3, 0, 0 }, + { 31, 0x7ffffee1, 0, 0 }, { 31, 0x7ffffedf, 0, 0 }, + { 31, 0x7ffffedd, 0, 0 }, { 31, 0x7ffffedb, 0, 0 }, + { 31, 0x7ffffed9, 0, 0 }, { 31, 0x7ffffed7, 0, 0 }, + { 31, 0x7ffffed5, 0, 0 }, { 31, 0x7ffffed3, 0, 0 }, + { 31, 0x7ffffed1, 0, 0 }, { 31, 0x7ffffecf, 0, 0 }, + { 31, 0x7ffffecd, 0, 0 }, { 31, 0x7ffffecb, 0, 0 }, + { 31, 0x7ffffec9, 0, 0 }, { 31, 0x7ffffec7, 0, 0 }, + { 31, 0x7ffffec5, 0, 0 }, { 31, 0x7ffffec3, 0, 0 }, + { 31, 0x7ffffec1, 0, 0 }, { 29, 0x1ffffff9, 7, 0x7f }, + { 29, 0x1ffffff9, 7, 0x7d }, { 29, 0x1ffffff9, 7, 0x7b }, + { 29, 0x1ffffff9, 7, 0x79 }, { 29, 0x1ffffff9, 7, 0x77 }, + { 29, 0x1ffffff9, 7, 0x75 }, { 29, 0x1ffffff9, 7, 0x73 }, + { 29, 0x1ffffff9, 7, 0x71 }, { 29, 0x1ffffff9, 7, 0x6f }, + { 29, 0x1ffffff9, 7, 0x6d }, { 29, 0x1ffffff9, 7, 0x6b }, + { 29, 0x1ffffff9, 7, 0x69 }, { 29, 0x1ffffff9, 7, 0x67 }, + { 29, 0x1ffffff9, 7, 0x65 }, { 29, 0x1ffffff9, 7, 0x63 }, + { 29, 0x1ffffff9, 7, 0x61 }, { 29, 0x1ffffff9, 7, 0x5f }, + { 29, 0x1ffffff9, 7, 0x5d }, { 29, 0x1ffffff9, 7, 0x5b }, + { 29, 0x1ffffff9, 7, 0x59 }, { 29, 0x1ffffff9, 7, 0x57 }, + { 29, 0x1ffffff9, 7, 0x55 }, { 29, 0x1ffffff9, 7, 0x53 }, + { 29, 0x1ffffff9, 7, 0x51 }, { 29, 0x1ffffff9, 7, 0x4f }, + { 29, 0x1ffffff9, 7, 0x4d }, { 29, 0x1ffffff9, 7, 0x4b }, + { 29, 0x1ffffff9, 7, 0x49 }, { 29, 0x1ffffff9, 7, 0x47 }, + { 29, 0x1ffffff9, 7, 0x45 }, { 29, 0x1ffffff9, 7, 0x43 }, + { 29, 0x1ffffff9, 7, 0x41 }, { 29, 0x1ffffff9, 7, 0x3f }, + { 29, 0x1ffffff9, 7, 0x3d }, { 29, 0x1ffffff9, 7, 0x3b }, + { 29, 0x1ffffff9, 7, 0x39 }, { 29, 0x1ffffff9, 7, 0x37 }, + { 29, 0x1ffffff9, 7, 0x35 }, { 29, 0x1ffffff9, 7, 0x33 }, + { 29, 0x1ffffff9, 7, 0x31 }, { 29, 0x1ffffff9, 7, 0x2f }, + { 29, 0x1ffffff9, 7, 0x2d }, { 29, 0x1ffffff9, 7, 0x2b }, + { 29, 0x1ffffff9, 7, 0x29 }, { 29, 0x1ffffff9, 7, 0x27 }, + { 29, 0x1ffffff9, 7, 0x25 }, { 29, 0x1ffffff9, 7, 0x23 }, + { 29, 0x1ffffff9, 7, 0x21 }, { 29, 0x1ffffff9, 7, 0x1f }, + { 29, 0x1ffffff9, 7, 0x1d }, { 29, 0x1ffffff9, 7, 0x1b }, + { 29, 0x1ffffff9, 7, 0x19 }, { 29, 0x1ffffff9, 7, 0x17 }, + { 29, 0x1ffffff9, 7, 0x15 }, { 29, 0x1ffffff9, 7, 0x13 }, + { 29, 0x1ffffff9, 7, 0x11 }, { 29, 0x1ffffff9, 7, 0xf }, + { 29, 0x1ffffff9, 7, 0xd }, { 29, 0x1ffffff9, 7, 0xb }, + { 29, 0x1ffffff9, 7, 0x9 }, { 29, 0x1ffffff9, 7, 0x7 }, + { 29, 0x1ffffff9, 7, 0x5 }, { 29, 0x1ffffff9, 7, 0x3 }, + { 29, 0x1ffffff9, 7, 0x1 }, { 0, 0, 0, 0 } + }, + + /* + * prefixed with 10 zeroes + */ + { + { 12, 0xff1, 0, 0 }, { 15, 0x7feb, 0, 0 }, + { 15, 0x7fe9, 0, 0 }, { 19, 0x7ffd7, 0, 0 }, + { 19, 0x7ffd5, 0, 0 }, { 19, 0x7ffd3, 0, 0 }, + { 19, 0x7ffd1, 0, 0 }, { 23, 0x7fffaf, 0, 0 }, + { 23, 0x7fffad, 0, 0 }, { 23, 0x7fffab, 0, 0 }, + { 23, 0x7fffa9, 0, 0 }, { 23, 0x7fffa7, 0, 0 }, + { 23, 0x7fffa5, 0, 0 }, { 23, 0x7fffa3, 0, 0 }, + { 23, 0x7fffa1, 0, 0 }, { 27, 0x7ffff7f, 0, 0 }, + { 27, 0x7ffff7d, 0, 0 }, { 27, 0x7ffff7b, 0, 0 }, + { 27, 0x7ffff79, 0, 0 }, { 27, 0x7ffff77, 0, 0 }, + { 27, 0x7ffff75, 0, 0 }, { 27, 0x7ffff73, 0, 0 }, + { 27, 0x7ffff71, 0, 0 }, { 27, 0x7ffff6f, 0, 0 }, + { 27, 0x7ffff6d, 0, 0 }, { 27, 0x7ffff6b, 0, 0 }, + { 27, 0x7ffff69, 0, 0 }, { 27, 0x7ffff67, 0, 0 }, + { 27, 0x7ffff65, 0, 0 }, { 27, 0x7ffff63, 0, 0 }, + { 27, 0x7ffff61, 0, 0 }, { 32, 0xfffffe3f, 0, 0 }, + { 32, 0xfffffe3d, 0, 0 }, { 32, 0xfffffe3b, 0, 0 }, + { 32, 0xfffffe39, 0, 0 }, { 32, 0xfffffe37, 0, 0 }, + { 32, 0xfffffe35, 0, 0 }, { 32, 0xfffffe33, 0, 0 }, + { 32, 0xfffffe31, 0, 0 }, { 32, 0xfffffe2f, 0, 0 }, + { 32, 0xfffffe2d, 0, 0 }, { 32, 0xfffffe2b, 0, 0 }, + { 32, 0xfffffe29, 0, 0 }, { 32, 0xfffffe27, 0, 0 }, + { 32, 0xfffffe25, 0, 0 }, { 32, 0xfffffe23, 0, 0 }, + { 32, 0xfffffe21, 0, 0 }, { 32, 0xfffffe1f, 0, 0 }, + { 32, 0xfffffe1d, 0, 0 }, { 32, 0xfffffe1b, 0, 0 }, + { 32, 0xfffffe19, 0, 0 }, { 32, 0xfffffe17, 0, 0 }, + { 32, 0xfffffe15, 0, 0 }, { 32, 0xfffffe13, 0, 0 }, + { 32, 0xfffffe11, 0, 0 }, { 32, 0xfffffe0f, 0, 0 }, + { 32, 0xfffffe0d, 0, 0 }, { 32, 0xfffffe0b, 0, 0 }, + { 32, 0xfffffe09, 0, 0 }, { 32, 0xfffffe07, 0, 0 }, + { 32, 0xfffffe05, 0, 0 }, { 32, 0xfffffe03, 0, 0 }, + { 32, 0xfffffe01, 0, 0 }, { 29, 0x1ffffffa, 7, 0x7f }, + { 29, 0x1ffffffa, 7, 0x7d }, { 29, 0x1ffffffa, 7, 0x7b }, + { 29, 0x1ffffffa, 7, 0x79 }, { 29, 0x1ffffffa, 7, 0x77 }, + { 29, 0x1ffffffa, 7, 0x75 }, { 29, 0x1ffffffa, 7, 0x73 }, + { 29, 0x1ffffffa, 7, 0x71 }, { 29, 0x1ffffffa, 7, 0x6f }, + { 29, 0x1ffffffa, 7, 0x6d }, { 29, 0x1ffffffa, 7, 0x6b }, + { 29, 0x1ffffffa, 7, 0x69 }, { 29, 0x1ffffffa, 7, 0x67 }, + { 29, 0x1ffffffa, 7, 0x65 }, { 29, 0x1ffffffa, 7, 0x63 }, + { 29, 0x1ffffffa, 7, 0x61 }, { 29, 0x1ffffffa, 7, 0x5f }, + { 29, 0x1ffffffa, 7, 0x5d }, { 29, 0x1ffffffa, 7, 0x5b }, + { 29, 0x1ffffffa, 7, 0x59 }, { 29, 0x1ffffffa, 7, 0x57 }, + { 29, 0x1ffffffa, 7, 0x55 }, { 29, 0x1ffffffa, 7, 0x53 }, + { 29, 0x1ffffffa, 7, 0x51 }, { 29, 0x1ffffffa, 7, 0x4f }, + { 29, 0x1ffffffa, 7, 0x4d }, { 29, 0x1ffffffa, 7, 0x4b }, + { 29, 0x1ffffffa, 7, 0x49 }, { 29, 0x1ffffffa, 7, 0x47 }, + { 29, 0x1ffffffa, 7, 0x45 }, { 29, 0x1ffffffa, 7, 0x43 }, + { 29, 0x1ffffffa, 7, 0x41 }, { 29, 0x1ffffffa, 7, 0x3f }, + { 29, 0x1ffffffa, 7, 0x3d }, { 29, 0x1ffffffa, 7, 0x3b }, + { 29, 0x1ffffffa, 7, 0x39 }, { 29, 0x1ffffffa, 7, 0x37 }, + { 29, 0x1ffffffa, 7, 0x35 }, { 29, 0x1ffffffa, 7, 0x33 }, + { 29, 0x1ffffffa, 7, 0x31 }, { 29, 0x1ffffffa, 7, 0x2f }, + { 29, 0x1ffffffa, 7, 0x2d }, { 29, 0x1ffffffa, 7, 0x2b }, + { 29, 0x1ffffffa, 7, 0x29 }, { 29, 0x1ffffffa, 7, 0x27 }, + { 29, 0x1ffffffa, 7, 0x25 }, { 29, 0x1ffffffa, 7, 0x23 }, + { 29, 0x1ffffffa, 7, 0x21 }, { 29, 0x1ffffffa, 7, 0x1f }, + { 29, 0x1ffffffa, 7, 0x1d }, { 29, 0x1ffffffa, 7, 0x1b }, + { 29, 0x1ffffffa, 7, 0x19 }, { 29, 0x1ffffffa, 7, 0x17 }, + { 29, 0x1ffffffa, 7, 0x15 }, { 29, 0x1ffffffa, 7, 0x13 }, + { 29, 0x1ffffffa, 7, 0x11 }, { 29, 0x1ffffffa, 7, 0xf }, + { 29, 0x1ffffffa, 7, 0xd }, { 29, 0x1ffffffa, 7, 0xb }, + { 29, 0x1ffffffa, 7, 0x9 }, { 29, 0x1ffffffa, 7, 0x7 }, + { 29, 0x1ffffffa, 7, 0x5 }, { 29, 0x1ffffffa, 7, 0x3 }, + { 29, 0x1ffffffa, 7, 0x1 }, { 0, 0, 0, 0 } + }, + + /* + * prefixed with 11 zeroes + */ + { + { 12, 0xff3, 0, 0 }, { 15, 0x7fef, 0, 0 }, + { 15, 0x7fed, 0, 0 }, { 19, 0x7ffdf, 0, 0 }, + { 19, 0x7ffdd, 0, 0 }, { 19, 0x7ffdb, 0, 0 }, + { 19, 0x7ffd9, 0, 0 }, { 23, 0x7fffbf, 0, 0 }, + { 23, 0x7fffbd, 0, 0 }, { 23, 0x7fffbb, 0, 0 }, + { 23, 0x7fffb9, 0, 0 }, { 23, 0x7fffb7, 0, 0 }, + { 23, 0x7fffb5, 0, 0 }, { 23, 0x7fffb3, 0, 0 }, + { 23, 0x7fffb1, 0, 0 }, { 28, 0xfffff1f, 0, 0 }, + { 28, 0xfffff1d, 0, 0 }, { 28, 0xfffff1b, 0, 0 }, + { 28, 0xfffff19, 0, 0 }, { 28, 0xfffff17, 0, 0 }, + { 28, 0xfffff15, 0, 0 }, { 28, 0xfffff13, 0, 0 }, + { 28, 0xfffff11, 0, 0 }, { 28, 0xfffff0f, 0, 0 }, + { 28, 0xfffff0d, 0, 0 }, { 28, 0xfffff0b, 0, 0 }, + { 28, 0xfffff09, 0, 0 }, { 28, 0xfffff07, 0, 0 }, + { 28, 0xfffff05, 0, 0 }, { 28, 0xfffff03, 0, 0 }, + { 28, 0xfffff01, 0, 0 }, { 32, 0xfffffe7f, 0, 0 }, + { 32, 0xfffffe7d, 0, 0 }, { 32, 0xfffffe7b, 0, 0 }, + { 32, 0xfffffe79, 0, 0 }, { 32, 0xfffffe77, 0, 0 }, + { 32, 0xfffffe75, 0, 0 }, { 32, 0xfffffe73, 0, 0 }, + { 32, 0xfffffe71, 0, 0 }, { 32, 0xfffffe6f, 0, 0 }, + { 32, 0xfffffe6d, 0, 0 }, { 32, 0xfffffe6b, 0, 0 }, + { 32, 0xfffffe69, 0, 0 }, { 32, 0xfffffe67, 0, 0 }, + { 32, 0xfffffe65, 0, 0 }, { 32, 0xfffffe63, 0, 0 }, + { 32, 0xfffffe61, 0, 0 }, { 32, 0xfffffe5f, 0, 0 }, + { 32, 0xfffffe5d, 0, 0 }, { 32, 0xfffffe5b, 0, 0 }, + { 32, 0xfffffe59, 0, 0 }, { 32, 0xfffffe57, 0, 0 }, + { 32, 0xfffffe55, 0, 0 }, { 32, 0xfffffe53, 0, 0 }, + { 32, 0xfffffe51, 0, 0 }, { 32, 0xfffffe4f, 0, 0 }, + { 32, 0xfffffe4d, 0, 0 }, { 32, 0xfffffe4b, 0, 0 }, + { 32, 0xfffffe49, 0, 0 }, { 32, 0xfffffe47, 0, 0 }, + { 32, 0xfffffe45, 0, 0 }, { 32, 0xfffffe43, 0, 0 }, + { 32, 0xfffffe41, 0, 0 }, { 29, 0x1ffffffb, 7, 0x7f }, + { 29, 0x1ffffffb, 7, 0x7d }, { 29, 0x1ffffffb, 7, 0x7b }, + { 29, 0x1ffffffb, 7, 0x79 }, { 29, 0x1ffffffb, 7, 0x77 }, + { 29, 0x1ffffffb, 7, 0x75 }, { 29, 0x1ffffffb, 7, 0x73 }, + { 29, 0x1ffffffb, 7, 0x71 }, { 29, 0x1ffffffb, 7, 0x6f }, + { 29, 0x1ffffffb, 7, 0x6d }, { 29, 0x1ffffffb, 7, 0x6b }, + { 29, 0x1ffffffb, 7, 0x69 }, { 29, 0x1ffffffb, 7, 0x67 }, + { 29, 0x1ffffffb, 7, 0x65 }, { 29, 0x1ffffffb, 7, 0x63 }, + { 29, 0x1ffffffb, 7, 0x61 }, { 29, 0x1ffffffb, 7, 0x5f }, + { 29, 0x1ffffffb, 7, 0x5d }, { 29, 0x1ffffffb, 7, 0x5b }, + { 29, 0x1ffffffb, 7, 0x59 }, { 29, 0x1ffffffb, 7, 0x57 }, + { 29, 0x1ffffffb, 7, 0x55 }, { 29, 0x1ffffffb, 7, 0x53 }, + { 29, 0x1ffffffb, 7, 0x51 }, { 29, 0x1ffffffb, 7, 0x4f }, + { 29, 0x1ffffffb, 7, 0x4d }, { 29, 0x1ffffffb, 7, 0x4b }, + { 29, 0x1ffffffb, 7, 0x49 }, { 29, 0x1ffffffb, 7, 0x47 }, + { 29, 0x1ffffffb, 7, 0x45 }, { 29, 0x1ffffffb, 7, 0x43 }, + { 29, 0x1ffffffb, 7, 0x41 }, { 29, 0x1ffffffb, 7, 0x3f }, + { 29, 0x1ffffffb, 7, 0x3d }, { 29, 0x1ffffffb, 7, 0x3b }, + { 29, 0x1ffffffb, 7, 0x39 }, { 29, 0x1ffffffb, 7, 0x37 }, + { 29, 0x1ffffffb, 7, 0x35 }, { 29, 0x1ffffffb, 7, 0x33 }, + { 29, 0x1ffffffb, 7, 0x31 }, { 29, 0x1ffffffb, 7, 0x2f }, + { 29, 0x1ffffffb, 7, 0x2d }, { 29, 0x1ffffffb, 7, 0x2b }, + { 29, 0x1ffffffb, 7, 0x29 }, { 29, 0x1ffffffb, 7, 0x27 }, + { 29, 0x1ffffffb, 7, 0x25 }, { 29, 0x1ffffffb, 7, 0x23 }, + { 29, 0x1ffffffb, 7, 0x21 }, { 29, 0x1ffffffb, 7, 0x1f }, + { 29, 0x1ffffffb, 7, 0x1d }, { 29, 0x1ffffffb, 7, 0x1b }, + { 29, 0x1ffffffb, 7, 0x19 }, { 29, 0x1ffffffb, 7, 0x17 }, + { 29, 0x1ffffffb, 7, 0x15 }, { 29, 0x1ffffffb, 7, 0x13 }, + { 29, 0x1ffffffb, 7, 0x11 }, { 29, 0x1ffffffb, 7, 0xf }, + { 29, 0x1ffffffb, 7, 0xd }, { 29, 0x1ffffffb, 7, 0xb }, + { 29, 0x1ffffffb, 7, 0x9 }, { 29, 0x1ffffffb, 7, 0x7 }, + { 29, 0x1ffffffb, 7, 0x5 }, { 29, 0x1ffffffb, 7, 0x3 }, + { 29, 0x1ffffffb, 7, 0x1 }, { 0, 0, 0, 0 } + }, + + /* + * prefixed with 12 zeroes + */ + { + { 12, 0xff5, 0, 0 }, { 16, 0xffe3, 0, 0 }, + { 16, 0xffe1, 0, 0 }, { 20, 0xfffc7, 0, 0 }, + { 20, 0xfffc5, 0, 0 }, { 20, 0xfffc3, 0, 0 }, + { 20, 0xfffc1, 0, 0 }, { 24, 0xffff8f, 0, 0 }, + { 24, 0xffff8d, 0, 0 }, { 24, 0xffff8b, 0, 0 }, + { 24, 0xffff89, 0, 0 }, { 24, 0xffff87, 0, 0 }, + { 24, 0xffff85, 0, 0 }, { 24, 0xffff83, 0, 0 }, + { 24, 0xffff81, 0, 0 }, { 28, 0xfffff3f, 0, 0 }, + { 28, 0xfffff3d, 0, 0 }, { 28, 0xfffff3b, 0, 0 }, + { 28, 0xfffff39, 0, 0 }, { 28, 0xfffff37, 0, 0 }, + { 28, 0xfffff35, 0, 0 }, { 28, 0xfffff33, 0, 0 }, + { 28, 0xfffff31, 0, 0 }, { 28, 0xfffff2f, 0, 0 }, + { 28, 0xfffff2d, 0, 0 }, { 28, 0xfffff2b, 0, 0 }, + { 28, 0xfffff29, 0, 0 }, { 28, 0xfffff27, 0, 0 }, + { 28, 0xfffff25, 0, 0 }, { 28, 0xfffff23, 0, 0 }, + { 28, 0xfffff21, 0, 0 }, { 32, 0xfffffebf, 0, 0 }, + { 32, 0xfffffebd, 0, 0 }, { 32, 0xfffffebb, 0, 0 }, + { 32, 0xfffffeb9, 0, 0 }, { 32, 0xfffffeb7, 0, 0 }, + { 32, 0xfffffeb5, 0, 0 }, { 32, 0xfffffeb3, 0, 0 }, + { 32, 0xfffffeb1, 0, 0 }, { 32, 0xfffffeaf, 0, 0 }, + { 32, 0xfffffead, 0, 0 }, { 32, 0xfffffeab, 0, 0 }, + { 32, 0xfffffea9, 0, 0 }, { 32, 0xfffffea7, 0, 0 }, + { 32, 0xfffffea5, 0, 0 }, { 32, 0xfffffea3, 0, 0 }, + { 32, 0xfffffea1, 0, 0 }, { 32, 0xfffffe9f, 0, 0 }, + { 32, 0xfffffe9d, 0, 0 }, { 32, 0xfffffe9b, 0, 0 }, + { 32, 0xfffffe99, 0, 0 }, { 32, 0xfffffe97, 0, 0 }, + { 32, 0xfffffe95, 0, 0 }, { 32, 0xfffffe93, 0, 0 }, + { 32, 0xfffffe91, 0, 0 }, { 32, 0xfffffe8f, 0, 0 }, + { 32, 0xfffffe8d, 0, 0 }, { 32, 0xfffffe8b, 0, 0 }, + { 32, 0xfffffe89, 0, 0 }, { 32, 0xfffffe87, 0, 0 }, + { 32, 0xfffffe85, 0, 0 }, { 32, 0xfffffe83, 0, 0 }, + { 32, 0xfffffe81, 0, 0 }, { 30, 0x1fff7400, 7, 0x7f }, + { 30, 0x1fff7400, 7, 0x7d }, { 30, 0x1fff7400, 7, 0x7b }, + { 30, 0x1fff7400, 7, 0x79 }, { 30, 0x1fff7400, 7, 0x77 }, + { 30, 0x1fff7400, 7, 0x75 }, { 30, 0x1fff7400, 7, 0x73 }, + { 30, 0x1fff7400, 7, 0x71 }, { 30, 0x1fff7400, 7, 0x6f }, + { 30, 0x1fff7400, 7, 0x6d }, { 30, 0x1fff7400, 7, 0x6b }, + { 30, 0x1fff7400, 7, 0x69 }, { 30, 0x1fff7400, 7, 0x67 }, + { 30, 0x1fff7400, 7, 0x65 }, { 30, 0x1fff7400, 7, 0x63 }, + { 30, 0x1fff7400, 7, 0x61 }, { 30, 0x1fff7400, 7, 0x5f }, + { 30, 0x1fff7400, 7, 0x5d }, { 30, 0x1fff7400, 7, 0x5b }, + { 30, 0x1fff7400, 7, 0x59 }, { 30, 0x1fff7400, 7, 0x57 }, + { 30, 0x1fff7400, 7, 0x55 }, { 30, 0x1fff7400, 7, 0x53 }, + { 30, 0x1fff7400, 7, 0x51 }, { 30, 0x1fff7400, 7, 0x4f }, + { 30, 0x1fff7400, 7, 0x4d }, { 30, 0x1fff7400, 7, 0x4b }, + { 30, 0x1fff7400, 7, 0x49 }, { 30, 0x1fff7400, 7, 0x47 }, + { 30, 0x1fff7400, 7, 0x45 }, { 30, 0x1fff7400, 7, 0x43 }, + { 30, 0x1fff7400, 7, 0x41 }, { 30, 0x1fff7400, 7, 0x3f }, + { 30, 0x1fff7400, 7, 0x3d }, { 30, 0x1fff7400, 7, 0x3b }, + { 30, 0x1fff7400, 7, 0x39 }, { 30, 0x1fff7400, 7, 0x37 }, + { 30, 0x1fff7400, 7, 0x35 }, { 30, 0x1fff7400, 7, 0x33 }, + { 30, 0x1fff7400, 7, 0x31 }, { 30, 0x1fff7400, 7, 0x2f }, + { 30, 0x1fff7400, 7, 0x2d }, { 30, 0x1fff7400, 7, 0x2b }, + { 30, 0x1fff7400, 7, 0x29 }, { 30, 0x1fff7400, 7, 0x27 }, + { 30, 0x1fff7400, 7, 0x25 }, { 30, 0x1fff7400, 7, 0x23 }, + { 30, 0x1fff7400, 7, 0x21 }, { 30, 0x1fff7400, 7, 0x1f }, + { 30, 0x1fff7400, 7, 0x1d }, { 30, 0x1fff7400, 7, 0x1b }, + { 30, 0x1fff7400, 7, 0x19 }, { 30, 0x1fff7400, 7, 0x17 }, + { 30, 0x1fff7400, 7, 0x15 }, { 30, 0x1fff7400, 7, 0x13 }, + { 30, 0x1fff7400, 7, 0x11 }, { 30, 0x1fff7400, 7, 0xf }, + { 30, 0x1fff7400, 7, 0xd }, { 30, 0x1fff7400, 7, 0xb }, + { 30, 0x1fff7400, 7, 0x9 }, { 30, 0x1fff7400, 7, 0x7 }, + { 30, 0x1fff7400, 7, 0x5 }, { 30, 0x1fff7400, 7, 0x3 }, + { 30, 0x1fff7400, 7, 0x1 }, { 0, 0, 0, 0 } + }, + + /* + * prefixed with 13 zeroes + */ + { + { 12, 0xff7, 0, 0 }, { 16, 0xffe7, 0, 0 }, + { 16, 0xffe5, 0, 0 }, { 20, 0xfffcf, 0, 0 }, + { 20, 0xfffcd, 0, 0 }, { 20, 0xfffcb, 0, 0 }, + { 20, 0xfffc9, 0, 0 }, { 24, 0xffff9f, 0, 0 }, + { 24, 0xffff9d, 0, 0 }, { 24, 0xffff9b, 0, 0 }, + { 24, 0xffff99, 0, 0 }, { 24, 0xffff97, 0, 0 }, + { 24, 0xffff95, 0, 0 }, { 24, 0xffff93, 0, 0 }, + { 24, 0xffff91, 0, 0 }, { 28, 0xfffff5f, 0, 0 }, + { 28, 0xfffff5d, 0, 0 }, { 28, 0xfffff5b, 0, 0 }, + { 28, 0xfffff59, 0, 0 }, { 28, 0xfffff57, 0, 0 }, + { 28, 0xfffff55, 0, 0 }, { 28, 0xfffff53, 0, 0 }, + { 28, 0xfffff51, 0, 0 }, { 28, 0xfffff4f, 0, 0 }, + { 28, 0xfffff4d, 0, 0 }, { 28, 0xfffff4b, 0, 0 }, + { 28, 0xfffff49, 0, 0 }, { 28, 0xfffff47, 0, 0 }, + { 28, 0xfffff45, 0, 0 }, { 28, 0xfffff43, 0, 0 }, + { 28, 0xfffff41, 0, 0 }, { 32, 0xfffffeff, 0, 0 }, + { 32, 0xfffffefd, 0, 0 }, { 32, 0xfffffefb, 0, 0 }, + { 32, 0xfffffef9, 0, 0 }, { 32, 0xfffffef7, 0, 0 }, + { 32, 0xfffffef5, 0, 0 }, { 32, 0xfffffef3, 0, 0 }, + { 32, 0xfffffef1, 0, 0 }, { 32, 0xfffffeef, 0, 0 }, + { 32, 0xfffffeed, 0, 0 }, { 32, 0xfffffeeb, 0, 0 }, + { 32, 0xfffffee9, 0, 0 }, { 32, 0xfffffee7, 0, 0 }, + { 32, 0xfffffee5, 0, 0 }, { 32, 0xfffffee3, 0, 0 }, + { 32, 0xfffffee1, 0, 0 }, { 32, 0xfffffedf, 0, 0 }, + { 32, 0xfffffedd, 0, 0 }, { 32, 0xfffffedb, 0, 0 }, + { 32, 0xfffffed9, 0, 0 }, { 32, 0xfffffed7, 0, 0 }, + { 32, 0xfffffed5, 0, 0 }, { 32, 0xfffffed3, 0, 0 }, + { 32, 0xfffffed1, 0, 0 }, { 32, 0xfffffecf, 0, 0 }, + { 32, 0xfffffecd, 0, 0 }, { 32, 0xfffffecb, 0, 0 }, + { 32, 0xfffffec9, 0, 0 }, { 32, 0xfffffec7, 0, 0 }, + { 32, 0xfffffec5, 0, 0 }, { 32, 0xfffffec3, 0, 0 }, + { 32, 0xfffffec1, 0, 0 }, { 30, 0x3ffffff9, 7, 0x7f }, + { 30, 0x3ffffff9, 7, 0x7d }, { 30, 0x3ffffff9, 7, 0x7b }, + { 30, 0x3ffffff9, 7, 0x79 }, { 30, 0x3ffffff9, 7, 0x77 }, + { 30, 0x3ffffff9, 7, 0x75 }, { 30, 0x3ffffff9, 7, 0x73 }, + { 30, 0x3ffffff9, 7, 0x71 }, { 30, 0x3ffffff9, 7, 0x6f }, + { 30, 0x3ffffff9, 7, 0x6d }, { 30, 0x3ffffff9, 7, 0x6b }, + { 30, 0x3ffffff9, 7, 0x69 }, { 30, 0x3ffffff9, 7, 0x67 }, + { 30, 0x3ffffff9, 7, 0x65 }, { 30, 0x3ffffff9, 7, 0x63 }, + { 30, 0x3ffffff9, 7, 0x61 }, { 30, 0x3ffffff9, 7, 0x5f }, + { 30, 0x3ffffff9, 7, 0x5d }, { 30, 0x3ffffff9, 7, 0x5b }, + { 30, 0x3ffffff9, 7, 0x59 }, { 30, 0x3ffffff9, 7, 0x57 }, + { 30, 0x3ffffff9, 7, 0x55 }, { 30, 0x3ffffff9, 7, 0x53 }, + { 30, 0x3ffffff9, 7, 0x51 }, { 30, 0x3ffffff9, 7, 0x4f }, + { 30, 0x3ffffff9, 7, 0x4d }, { 30, 0x3ffffff9, 7, 0x4b }, + { 30, 0x3ffffff9, 7, 0x49 }, { 30, 0x3ffffff9, 7, 0x47 }, + { 30, 0x3ffffff9, 7, 0x45 }, { 30, 0x3ffffff9, 7, 0x43 }, + { 30, 0x3ffffff9, 7, 0x41 }, { 30, 0x3ffffff9, 7, 0x3f }, + { 30, 0x3ffffff9, 7, 0x3d }, { 30, 0x3ffffff9, 7, 0x3b }, + { 30, 0x3ffffff9, 7, 0x39 }, { 30, 0x3ffffff9, 7, 0x37 }, + { 30, 0x3ffffff9, 7, 0x35 }, { 30, 0x3ffffff9, 7, 0x33 }, + { 30, 0x3ffffff9, 7, 0x31 }, { 30, 0x3ffffff9, 7, 0x2f }, + { 30, 0x3ffffff9, 7, 0x2d }, { 30, 0x3ffffff9, 7, 0x2b }, + { 30, 0x3ffffff9, 7, 0x29 }, { 30, 0x3ffffff9, 7, 0x27 }, + { 30, 0x3ffffff9, 7, 0x25 }, { 30, 0x3ffffff9, 7, 0x23 }, + { 30, 0x3ffffff9, 7, 0x21 }, { 30, 0x3ffffff9, 7, 0x1f }, + { 30, 0x3ffffff9, 7, 0x1d }, { 30, 0x3ffffff9, 7, 0x1b }, + { 30, 0x3ffffff9, 7, 0x19 }, { 30, 0x3ffffff9, 7, 0x17 }, + { 30, 0x3ffffff9, 7, 0x15 }, { 30, 0x3ffffff9, 7, 0x13 }, + { 30, 0x3ffffff9, 7, 0x11 }, { 30, 0x3ffffff9, 7, 0xf }, + { 30, 0x3ffffff9, 7, 0xd }, { 30, 0x3ffffff9, 7, 0xb }, + { 30, 0x3ffffff9, 7, 0x9 }, { 30, 0x3ffffff9, 7, 0x7 }, + { 30, 0x3ffffff9, 7, 0x5 }, { 30, 0x3ffffff9, 7, 0x3 }, + { 30, 0x3ffffff9, 7, 0x1 }, { 0, 0, 0, 0 } + }, + + /* + * prefixed with 14 zeroes + */ + { + { 13, 0x1ff1, 0, 0 }, { 16, 0xffeb, 0, 0 }, + { 16, 0xffe9, 0, 0 }, { 20, 0xfffd7, 0, 0 }, + { 20, 0xfffd5, 0, 0 }, { 20, 0xfffd3, 0, 0 }, + { 20, 0xfffd1, 0, 0 }, { 24, 0xffffaf, 0, 0 }, + { 24, 0xffffad, 0, 0 }, { 24, 0xffffab, 0, 0 }, + { 24, 0xffffa9, 0, 0 }, { 24, 0xffffa7, 0, 0 }, + { 24, 0xffffa5, 0, 0 }, { 24, 0xffffa3, 0, 0 }, + { 24, 0xffffa1, 0, 0 }, { 28, 0xfffff7f, 0, 0 }, + { 28, 0xfffff7d, 0, 0 }, { 28, 0xfffff7b, 0, 0 }, + { 28, 0xfffff79, 0, 0 }, { 28, 0xfffff77, 0, 0 }, + { 28, 0xfffff75, 0, 0 }, { 28, 0xfffff73, 0, 0 }, + { 28, 0xfffff71, 0, 0 }, { 28, 0xfffff6f, 0, 0 }, + { 28, 0xfffff6d, 0, 0 }, { 28, 0xfffff6b, 0, 0 }, + { 28, 0xfffff69, 0, 0 }, { 28, 0xfffff67, 0, 0 }, + { 28, 0xfffff65, 0, 0 }, { 28, 0xfffff63, 0, 0 }, + { 28, 0xfffff61, 0, 0 }, { 27, 0x7fffff8, 6, 0x3f }, + { 27, 0x7fffff8, 6, 0x3d }, { 27, 0x7fffff8, 6, 0x3b }, + { 27, 0x7fffff8, 6, 0x39 }, { 27, 0x7fffff8, 6, 0x37 }, + { 27, 0x7fffff8, 6, 0x35 }, { 27, 0x7fffff8, 6, 0x33 }, + { 27, 0x7fffff8, 6, 0x31 }, { 27, 0x7fffff8, 6, 0x2f }, + { 27, 0x7fffff8, 6, 0x2d }, { 27, 0x7fffff8, 6, 0x2b }, + { 27, 0x7fffff8, 6, 0x29 }, { 27, 0x7fffff8, 6, 0x27 }, + { 27, 0x7fffff8, 6, 0x25 }, { 27, 0x7fffff8, 6, 0x23 }, + { 27, 0x7fffff8, 6, 0x21 }, { 27, 0x7fffff8, 6, 0x1f }, + { 27, 0x7fffff8, 6, 0x1d }, { 27, 0x7fffff8, 6, 0x1b }, + { 27, 0x7fffff8, 6, 0x19 }, { 27, 0x7fffff8, 6, 0x17 }, + { 27, 0x7fffff8, 6, 0x15 }, { 27, 0x7fffff8, 6, 0x13 }, + { 27, 0x7fffff8, 6, 0x11 }, { 27, 0x7fffff8, 6, 0xf }, + { 27, 0x7fffff8, 6, 0xd }, { 27, 0x7fffff8, 6, 0xb }, + { 27, 0x7fffff8, 6, 0x9 }, { 27, 0x7fffff8, 6, 0x7 }, + { 27, 0x7fffff8, 6, 0x5 }, { 27, 0x7fffff8, 6, 0x3 }, + { 27, 0x7fffff8, 6, 0x1 }, { 30, 0x3ffffffa, 7, 0x7f }, + { 30, 0x3ffffffa, 7, 0x7d }, { 30, 0x3ffffffa, 7, 0x7b }, + { 30, 0x3ffffffa, 7, 0x79 }, { 30, 0x3ffffffa, 7, 0x77 }, + { 30, 0x3ffffffa, 7, 0x75 }, { 30, 0x3ffffffa, 7, 0x73 }, + { 30, 0x3ffffffa, 7, 0x71 }, { 30, 0x3ffffffa, 7, 0x6f }, + { 30, 0x3ffffffa, 7, 0x6d }, { 30, 0x3ffffffa, 7, 0x6b }, + { 30, 0x3ffffffa, 7, 0x69 }, { 30, 0x3ffffffa, 7, 0x67 }, + { 30, 0x3ffffffa, 7, 0x65 }, { 30, 0x3ffffffa, 7, 0x63 }, + { 30, 0x3ffffffa, 7, 0x61 }, { 30, 0x3ffffffa, 7, 0x5f }, + { 30, 0x3ffffffa, 7, 0x5d }, { 30, 0x3ffffffa, 7, 0x5b }, + { 30, 0x3ffffffa, 7, 0x59 }, { 30, 0x3ffffffa, 7, 0x57 }, + { 30, 0x3ffffffa, 7, 0x55 }, { 30, 0x3ffffffa, 7, 0x53 }, + { 30, 0x3ffffffa, 7, 0x51 }, { 30, 0x3ffffffa, 7, 0x4f }, + { 30, 0x3ffffffa, 7, 0x4d }, { 30, 0x3ffffffa, 7, 0x4b }, + { 30, 0x3ffffffa, 7, 0x49 }, { 30, 0x3ffffffa, 7, 0x47 }, + { 30, 0x3ffffffa, 7, 0x45 }, { 30, 0x3ffffffa, 7, 0x43 }, + { 30, 0x3ffffffa, 7, 0x41 }, { 30, 0x3ffffffa, 7, 0x3f }, + { 30, 0x3ffffffa, 7, 0x3d }, { 30, 0x3ffffffa, 7, 0x3b }, + { 30, 0x3ffffffa, 7, 0x39 }, { 30, 0x3ffffffa, 7, 0x37 }, + { 30, 0x3ffffffa, 7, 0x35 }, { 30, 0x3ffffffa, 7, 0x33 }, + { 30, 0x3ffffffa, 7, 0x31 }, { 30, 0x3ffffffa, 7, 0x2f }, + { 30, 0x3ffffffa, 7, 0x2d }, { 30, 0x3ffffffa, 7, 0x2b }, + { 30, 0x3ffffffa, 7, 0x29 }, { 30, 0x3ffffffa, 7, 0x27 }, + { 30, 0x3ffffffa, 7, 0x25 }, { 30, 0x3ffffffa, 7, 0x23 }, + { 30, 0x3ffffffa, 7, 0x21 }, { 30, 0x3ffffffa, 7, 0x1f }, + { 30, 0x3ffffffa, 7, 0x1d }, { 30, 0x3ffffffa, 7, 0x1b }, + { 30, 0x3ffffffa, 7, 0x19 }, { 30, 0x3ffffffa, 7, 0x17 }, + { 30, 0x3ffffffa, 7, 0x15 }, { 30, 0x3ffffffa, 7, 0x13 }, + { 30, 0x3ffffffa, 7, 0x11 }, { 30, 0x3ffffffa, 7, 0xf }, + { 30, 0x3ffffffa, 7, 0xd }, { 30, 0x3ffffffa, 7, 0xb }, + { 30, 0x3ffffffa, 7, 0x9 }, { 30, 0x3ffffffa, 7, 0x7 }, + { 30, 0x3ffffffa, 7, 0x5 }, { 30, 0x3ffffffa, 7, 0x3 }, + { 30, 0x3ffffffa, 7, 0x1 }, { 0, 0, 0, 0 } + }, + + /* + * prefixed with 15 zeroes + */ + { + { 13, 0x1ff3, 0, 0 }, { 2, 0x3, 0, 0 }, + { 2, 0x1, 0, 0 }, { 3, 0x7, 0, 0 }, + { 3, 0x5, 0, 0 }, { 3, 0x3, 0, 0 }, + { 3, 0x1, 0, 0 }, { 31, 0x7ffffffb, 4, 0xf }, + { 31, 0x7ffffffb, 4, 0xd }, { 31, 0x7ffffffb, 4, 0xb }, + { 31, 0x7ffffffb, 4, 0x9 }, { 31, 0x7ffffffb, 4, 0x7 }, + { 31, 0x7ffffffb, 4, 0x5 }, { 31, 0x7ffffffb, 4, 0x3 }, + { 31, 0x7ffffffb, 4, 0x1 }, { 5, 0x1f, 0, 0 }, + { 5, 0x1d, 0, 0 }, { 5, 0x1b, 0, 0 }, + { 5, 0x19, 0, 0 }, { 5, 0x17, 0, 0 }, + { 5, 0x15, 0, 0 }, { 5, 0x13, 0, 0 }, + { 5, 0x11, 0, 0 }, { 5, 0xf, 0, 0 }, + { 5, 0xd, 0, 0 }, { 5, 0xb, 0, 0 }, + { 5, 0x9, 0, 0 }, { 5, 0x7, 0, 0 }, + { 5, 0x5, 0, 0 }, { 5, 0x3, 0, 0 }, + { 5, 0x1, 0, 0 }, { 6, 0x3f, 0, 0 }, + { 6, 0x3d, 0, 0 }, { 6, 0x3b, 0, 0 }, + { 6, 0x39, 0, 0 }, { 6, 0x37, 0, 0 }, + { 6, 0x35, 0, 0 }, { 6, 0x33, 0, 0 }, + { 6, 0x31, 0, 0 }, { 6, 0x2f, 0, 0 }, + { 6, 0x2d, 0, 0 }, { 6, 0x2b, 0, 0 }, + { 6, 0x29, 0, 0 }, { 6, 0x27, 0, 0 }, + { 6, 0x25, 0, 0 }, { 6, 0x23, 0, 0 }, + { 6, 0x21, 0, 0 }, { 6, 0x1f, 0, 0 }, + { 6, 0x1d, 0, 0 }, { 6, 0x1b, 0, 0 }, + { 6, 0x19, 0, 0 }, { 6, 0x17, 0, 0 }, + { 6, 0x15, 0, 0 }, { 6, 0x13, 0, 0 }, + { 6, 0x11, 0, 0 }, { 6, 0xf, 0, 0 }, + { 6, 0xd, 0, 0 }, { 6, 0xb, 0, 0 }, + { 6, 0x9, 0, 0 }, { 6, 0x7, 0, 0 }, + { 6, 0x5, 0, 0 }, { 6, 0x3, 0, 0 }, + { 6, 0x1, 0, 0 }, { 7, 0x7f, 0, 0 }, + { 7, 0x7d, 0, 0 }, { 7, 0x7b, 0, 0 }, + { 7, 0x79, 0, 0 }, { 7, 0x77, 0, 0 }, + { 7, 0x75, 0, 0 }, { 7, 0x73, 0, 0 }, + { 7, 0x71, 0, 0 }, { 7, 0x6f, 0, 0 }, + { 7, 0x6d, 0, 0 }, { 7, 0x6b, 0, 0 }, + { 7, 0x69, 0, 0 }, { 7, 0x67, 0, 0 }, + { 7, 0x65, 0, 0 }, { 7, 0x63, 0, 0 }, + { 7, 0x61, 0, 0 }, { 7, 0x5f, 0, 0 }, + { 7, 0x5d, 0, 0 }, { 7, 0x5b, 0, 0 }, + { 7, 0x59, 0, 0 }, { 7, 0x57, 0, 0 }, + { 7, 0x55, 0, 0 }, { 7, 0x53, 0, 0 }, + { 7, 0x51, 0, 0 }, { 7, 0x4f, 0, 0 }, + { 7, 0x4d, 0, 0 }, { 7, 0x4b, 0, 0 }, + { 7, 0x49, 0, 0 }, { 7, 0x47, 0, 0 }, + { 7, 0x45, 0, 0 }, { 7, 0x43, 0, 0 }, + { 7, 0x41, 0, 0 }, { 7, 0x3f, 0, 0 }, + { 7, 0x3d, 0, 0 }, { 7, 0x3b, 0, 0 }, + { 7, 0x39, 0, 0 }, { 7, 0x37, 0, 0 }, + { 7, 0x35, 0, 0 }, { 7, 0x33, 0, 0 }, + { 7, 0x31, 0, 0 }, { 7, 0x2f, 0, 0 }, + { 7, 0x2d, 0, 0 }, { 7, 0x2b, 0, 0 }, + { 7, 0x29, 0, 0 }, { 7, 0x27, 0, 0 }, + { 7, 0x25, 0, 0 }, { 7, 0x23, 0, 0 }, + { 7, 0x21, 0, 0 }, { 7, 0x1f, 0, 0 }, + { 7, 0x1d, 0, 0 }, { 7, 0x1b, 0, 0 }, + { 7, 0x19, 0, 0 }, { 7, 0x17, 0, 0 }, + { 7, 0x15, 0, 0 }, { 7, 0x13, 0, 0 }, + { 7, 0x11, 0, 0 }, { 7, 0xf, 0, 0 }, + { 7, 0xd, 0, 0 }, { 7, 0xb, 0, 0 }, + { 7, 0x9, 0, 0 }, { 7, 0x7, 0, 0 }, + { 7, 0x5, 0, 0 }, { 7, 0x3, 0, 0 }, + { 7, 0x1, 0, 0 }, { 0, 0, 0, 0 } + } +}; + +VlcMagic _magic_values[] = { + { 0x0, 0, 1 }, + { 0x1, 0, 2 }, + { 0x4, 0, 3 }, + { 0xB, 1, 1 }, + { 0xC, 0, 4 }, + { 0x1A, 0, 5 }, + { 0x1B, 2, 1 }, + { 0x38, 3, 1 }, + { 0x39, 1, 2 }, + { 0x3A, 1, 3 }, + { 0x3B, 0, 6 }, + { 0x78, 4, 1 }, + { 0x79, 5, 1 }, + { 0x7A, 6, 1 }, + { 0x7B, 2, 2 }, + { 0xF8, 1, 4 }, + { 0xF9, 7, 1 }, + { 0xFA, 8, 1 }, + { 0xFB, 3, 2 }, + { 0x1F8, 4, 2 }, + { 0x1F9, 5, 2 }, + { 0x1FA, 2, 3 }, + { 0x1FB, 2, 4 }, + { 0x3F8, 1, 5 }, + { 0x3F9, 1, 6 }, + { 0x3FA, 0, 7 }, + { 0x3FB, 9, 1 }, + { 0x7F8, 10, 1 }, + { 0x7F9, 11, 1 }, + { 0x7FA, 12, 1 }, + { 0x7FB, 13, 1 }, + { 0xFF8, 14, 1 }, + { 0xFF9, 15, 1 }, + { 0xFFA, 6, 2 }, + { 0xFFB, 7, 2 }, + { 0x1FF8, 8, 2 }, + { 0x1FF9, 9, 2 }, + { 0x1FFA, 10, 2 }, + { 0x1FFB, 11, 2 }, + { 0x3FF8, 12, 2 }, + { 0x3FF9, 13, 2 }, + { 0x3FFA, 14, 2 }, + { 0x3FFB, 3, 3 }, + { 0x7FF8, 4, 3 }, + { 0x7FF9, 5, 3 }, + { 0x7FFA, 6, 3 }, + { 0x7FFB, 7, 3 }, + { 0xFFF8, 8, 3 }, + { 0xFFF9, 9, 3 }, + { 0xFFFA, 10, 3 }, + { 0xFFFB, 11, 3 }, + { 0x1FFF8, 12, 3 }, + { 0x1FFF9, 13, 3 }, + { 0x1FFFA, 14, 3 }, + { 0x1FFFB, 3, 4 }, + { 0x3FFF8, 4, 4 }, + { 0x3FFF9, 5, 4 }, + { 0x3FFFA, 6, 4 }, + { 0x3FFFB, 7, 4 }, + { 0x7FFF8, 8, 4 }, + { 0x7FFF9, 9, 4 }, + { 0x7FFFA, 10, 4 }, + { 0x7FFFB, 11, 4 }, + { 0xFFFF8, 12, 4 }, + { 0xFFFF9, 13, 4 }, + { 0xFFFFA, 14, 4 }, + { 0xFFFFB, 2, 5 }, + { 0x1FFFF8, 3, 5 }, + { 0x1FFFF9, 4, 5 }, + { 0x1FFFFA, 5, 5 }, + { 0x1FFFFB, 6, 5 }, + { 0x3FFFF8, 7, 5 }, + { 0x3FFFF9, 8, 5 }, + { 0x3FFFFA, 9, 5 }, + { 0x3FFFFB, 10, 5 }, + { 0x7FFFF8, 11, 5 }, + { 0x7FFFF9, 12, 5 }, + { 0x7FFFFA, 13, 5 }, + { 0x7FFFFB, 14, 5 }, + { 0xFFFFF8, 2, 6 }, + { 0xFFFFF9, 3, 6 }, + { 0xFFFFFA, 4, 6 }, + { 0xFFFFFB, 5, 6 }, + { 0x1FFFFF8, 6, 6 }, + { 0x1FFFFF9, 7, 6 }, + { 0x1FFFFFA, 8, 6 }, + { 0x1FFFFFB, 9, 6 }, + { 0x3FFFFF8, 10, 6 }, + { 0x3FFFFF9, 11, 6 }, + { 0x3FFFFFA, 12, 6 }, + { 0x3FFFFFB, 13, 6 }, + { 0x7FFFFF8, 14, 6 }, + { 0x7FFFFF9, 1, 7 }, + { 0x7FFFFFA, 2, 7 }, + { 0x7FFFFFB, 3, 7 }, + { 0xFFFFFF8, 4, 7 }, + { 0xFFFFFF9, 5, 7 }, + { 0xFFFFFFA, 6, 7 }, + { 0xFFFFFFB, 7, 7 }, + { 0x1FFFFFF8, 8, 7 }, + { 0x1FFFFFF9, 9, 7 }, + { 0x1FFFFFFA, 10, 7 }, + { 0x1FFFFFFB, 11, 7 }, + { 0x3FFFFFF8, 12, 7 }, + { 0x3FFFFFF9, 13, 7 }, + { 0x3FFFFFFA, 14, 7 } +}; + +/* + * _find_magic + * + * Internal helper-function used to locate a given + * VlcMagic entry. + */ +VlcMagic *_find_magic(guint magic) +{ + gint low = 0; + gint high = sizeof(_magic_values) / sizeof(VlcMagic) - 1; + gint mid; + + while (low <= high) { + mid = (low + high) / 2; + + if (_magic_values[mid].magic < magic) + low = mid + 1; + else if (_magic_values[mid].magic > magic) + high = mid - 1; + else + return &_magic_values[mid]; + } + + return NULL; +} + +/* + * _initialize_vlcdec_lookup + * + * Internal helper-function used to initialize + * the lookup-table used by the VLC-decoder. + */ +void _initialize_vlcdec_lookup(gint8 *lookup_tbl) +{ + gint8 util_buf[3072]; + gint v1_start, v1_end, v1_dec, util_buf_offset; + gint util_buf_offset_inc, buf1_val, samples_offset; + gint v1, v2; + gint8 *p, *p1, *p2, *p3; + + util_buf[0] = 0; + util_buf[1] = 0; + util_buf[2] = 0; + util_buf[3] = 1; + util_buf[4] = 1; + util_buf[5] = 1; + util_buf[765] = 1; + util_buf[766] = 0; + util_buf[767] = 1; + lookup_tbl[255] = 255; + lookup_tbl[256] = 1; + + v1_start = -3; + v1_dec = 4; + + util_buf_offset = 11; + util_buf_offset_inc = 12; + buf1_val = 2; + + samples_offset = 509; + + do { + v1 = v1_start; + v1_end = -(abs(v1_start) + 1) / 2; + v2 = 0; + + p2 = util_buf + util_buf_offset - 3; + + do { + p1 = util_buf + ((v1 & 0xff) * 3); + p1[0] = buf1_val; + p1[1] = v2; + p1[2] = buf1_val; + + p2[1] = buf1_val; + p2[2] = v2 + 1; + p2[3] = buf1_val; + + p3 = lookup_tbl + samples_offset + v2 + 1; + p3[0] = v1 & 0xff; + p3[1] = -(v1 & 0xff); + + v1++; + v2 += 2; + p2 -= 3; + } while (v1 <= v1_end); + + v1_start -= v1_dec; + v1_dec *= 2; + + util_buf_offset += util_buf_offset_inc; + util_buf_offset_inc *= 2; + buf1_val++; + + samples_offset += 255; + } while (buf1_val <= 7); + + p = lookup_tbl + 1785 + util_buf[388]; + p[0] = 129; +} + diff --git a/kopete/protocols/msn/webcam/libmimic/vlc_decode.c b/kopete/protocols/msn/webcam/libmimic/vlc_decode.c new file mode 100644 index 00000000..5675342d --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/vlc_decode.c @@ -0,0 +1,119 @@ +/* Copyright (C) 2005 Ole André Vadla Ravnås <oleavr@gmail.com> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <string.h> +#include "mimic-private.h" + +extern guchar _col_zag[64]; + +/* + * _vlc_decode_block + * + * De-serialize (reconstruct) a variable length coded 8x8 block. + */ +gboolean _vlc_decode_block(MimCtx *ctx, gint *block, gint num_coeffs) +{ + guint pos; + + memset(block, 0, 64 * sizeof(gint)); + + /* The DC-value is read in as is. */ + block[0] = _read_bits(ctx, 8); + + for (pos = 1; pos < num_coeffs; pos++) { + + guint prev_data_index, prev_cur_chunk_len, prev_chunk; + guint value, num_bits; + gboolean prev_read_odd, found_magic; + + /* Save context. */ + prev_data_index = ctx->data_index; + prev_cur_chunk_len = ctx->cur_chunk_len; + prev_chunk = ctx->cur_chunk; + prev_read_odd = ctx->read_odd; + + /* Grab 16 bits. */ + value = _read_bits(ctx, 16) << 16; + + /* Restore context. */ + ctx->data_index = prev_data_index; + ctx->cur_chunk_len = prev_cur_chunk_len; + ctx->cur_chunk = prev_chunk; + ctx->read_odd = prev_read_odd; + + /* Analyze and determine number of bits to read initially. */ + num_bits = 3; + if ((value >> 30) == 0 || (value >> 30) == 1) { + num_bits = 2; + } else if ((value & 0xE0000000) != 0x80000000) { + guint nibble = value >> 28; + + if (nibble == 11 || nibble == 12) { + num_bits = 4; + } else if (nibble == 10) { + _read_bits(ctx, 4); + + return TRUE; + } else { + if (((value << 2) & 0x8000000) == 0) + num_bits = 2; + + num_bits += 2; + } + } + + /* Read that number of bits. */ + value = _read_bits(ctx, num_bits); + + /* + * Look up the current value against the magic ones, + * and continue extending it bit by bit from the input + * stream until the magic value is found or we have + * read 32 bits (in which case we give up). + */ + found_magic = FALSE; + while (!found_magic) { + VlcMagic *magic; + + if (num_bits > 32) + return FALSE; + + magic = _find_magic(value); + + if (magic != NULL) { + pos += magic->pos_add; + num_bits = magic->num_bits; + + found_magic = TRUE; + } else { + value <<= 1; + value |= _read_bits(ctx, 1); + + num_bits++; + } + } + + /* Read the number of bits given by magic value entry. */ + value = _read_bits(ctx, num_bits); + + /* Gotcha! :-) */ + block[_col_zag[pos]] = ctx->vlcdec_lookup[(num_bits * 255) + value]; + } + + return TRUE; +} + diff --git a/kopete/protocols/msn/webcam/libmimic/vlc_encode.c b/kopete/protocols/msn/webcam/libmimic/vlc_encode.c new file mode 100644 index 00000000..8d301627 --- /dev/null +++ b/kopete/protocols/msn/webcam/libmimic/vlc_encode.c @@ -0,0 +1,84 @@ +/* Copyright (C) 2005 Ole André Vadla RavnÃ¥s <oleavr@gmail.com> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include <stdlib.h> +#include "mimic-private.h" + +extern guchar _col_zag[64]; +extern VlcSymbol _vlc_alphabet[16][128]; + +/* + * _vlc_encode_block + * + * Serialize an 8x8 block using variable length coding. + */ +void _vlc_encode_block(MimCtx *ctx, const gint *block, gint num_coeffs) +{ + gint i, num_zeroes; + + /* The DC value is written out as is. */ + _write_bits(ctx, block[0], 8); + + /* Number of zeroes prefixing the next non-zero value. */ + num_zeroes = 0; + + for (i = 1; i < num_coeffs && num_zeroes <= 14; i++) { + + /* Fetch AC coefficients from block in zig-zag order. */ + gint value = block[_col_zag[i]]; + + if (value != 0) { + VlcSymbol sym; + + /* Clip input values to [-128, +128]. */ + if (value < -128) + value = -128; + else if (value > 128) + value = 128; + + /* Look up symbol for the current non-zero value. */ + sym = _vlc_alphabet[num_zeroes][abs(value) - 1]; + + /* No symbol? very rare... */ + if (sym.length1 <= 0) + break; + + /* The symbols for negative values are the same as for positives, minus one. */ + if (value < 0) { + if (sym.length2 > 0) + sym.part2 -= 1; + else + sym.part1 -= 1; + } + + /* Write out the full symbol. */ + _write_bits(ctx, sym.part1, sym.length1); + if (sym.length2 > 0) + _write_bits(ctx, sym.part2, sym.length2); + + /* Start counting zeroes again. */ + num_zeroes = 0; + } else { + num_zeroes++; + } + } + + /* Write out EOB if necessary. */ + if (num_zeroes > 0) + _write_bits(ctx, 0xA, 4); +} + |