694{
695 const unsigned char *sp;
696 const unsigned char *srcend;
697 unsigned char *dp;
698 unsigned char *destend;
699
700 sp = (
const unsigned char *)
source;
701 srcend = ((
const unsigned char *)
source) + slen;
702 dp = (
unsigned char *)
dest;
703 destend = dp + rawsize;
704
705 while (sp < srcend && dp < destend)
706 {
707 /*
708 * Read one control byte and process the next 8 items (or as many as
709 * remain in the compressed input).
710 */
711 unsigned char ctrl = *sp++;
712 int ctrlc;
713
714 for (ctrlc = 0; ctrlc < 8 && sp < srcend && dp < destend; ctrlc++)
715 {
716 if (ctrl & 1)
717 {
718 /*
719 * Set control bit means we must read a match tag. The match
720 * is coded with two bytes. First byte uses lower nibble to
721 * code length - 3. Higher nibble contains upper 4 bits of the
722 * offset. The next following byte contains the lower 8 bits
723 * of the offset. If the length is coded as 18, another
724 * extension tag byte tells how much longer the match really
725 * was (0-255).
726 */
729
730 len = (sp[0] & 0x0f) + 3;
731 off = ((sp[0] & 0xf0) << 4) | sp[1];
732 sp += 2;
735
736 /*
737 * Check for corrupt data: if we fell off the end of the
738 * source, or if we obtained off = 0, or if off is more than
739 * the distance back to the buffer start, we have problems.
740 * (We must check for off = 0, else we risk an infinite loop
741 * below in the face of corrupt data. Likewise, the upper
742 * limit on off prevents accessing outside the buffer
743 * boundaries.)
744 */
745 if (
unlikely(sp > srcend || off == 0 ||
746 off > (dp - (
unsigned char *)
dest)))
747 return -1;
748
749 /*
750 * Don't emit more data than requested.
751 */
753
754 /*
755 * Now we copy the bytes specified by the tag from OUTPUT to
756 * OUTPUT (copy len bytes from dp - off to dp). The copied
757 * areas could overlap, so to avoid undefined behavior in
758 * memcpy(), be careful to copy only non-overlapping regions.
759 *
760 * Note that we cannot use memmove() instead, since while its
761 * behavior is well-defined, it's also not what we want.
762 */
764 {
765 /*
766 * We can safely copy "off" bytes since that clearly
767 * results in non-overlapping source and destination.
768 */
769 memcpy(dp, dp - off, off);
771 dp += off;
772
773 /*----------
774 * This bit is less obvious: we can double "off" after
775 * each such step. Consider this raw input:
776 * 112341234123412341234
777 * This will be encoded as 5 literal bytes "11234" and
778 * then a match tag with length 16 and offset 4. After
779 * memcpy'ing the first 4 bytes, we will have emitted
780 * 112341234
781 * so we can double "off" to 8, then after the next step
782 * we have emitted
783 * 11234123412341234
784 * Then we can double "off" again, after which it is more
785 * than the remaining "len" so we fall out of this loop
786 * and finish with a non-overlapping copy of the
787 * remainder. In general, a match tag with off < len
788 * implies that the decoded data has a repeat length of
789 * "off". We can handle 1, 2, 4, etc repetitions of the
790 * repeated string per memcpy until we get to a situation
791 * where the final copy step is non-overlapping.
792 *
793 * (Another way to understand this is that we are keeping
794 * the copy source point dp - off the same throughout.)
795 *----------
796 */
797 off += off;
798 }
799 memcpy(dp, dp - off,
len);
801 }
802 else
803 {
804 /*
805 * An unset control bit means LITERAL BYTE. So we just copy
806 * one from INPUT to OUTPUT.
807 */
808 *dp++ = *sp++;
809 }
810
811 /*
812 * Advance the control bit
813 */
814 ctrl >>= 1;
815 }
816 }
817
818 /*
819 * If requested, check we decompressed the right amount.
820 */
821 if (check_complete && (dp != destend || sp != srcend))
822 return -1;
823
824 /*
825 * That's it.
826 */
827 return (
char *) dp -
dest;
828}