/*

  Copyright (C) 2004, 2008, 2011 Rocky Bernstein <rocky@gnu.org>

  Copyright (C) 1998 Monty xiphmont@mit.edu

  This program is free software: you can redistribute it and/or modify

  it under the terms of the GNU General Public License as published by

  the Free Software Foundation, either version 3 of the License, or

  (at your option) any later version.

  This program 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 General Public License for more details.

  You should have received a copy of the GNU General Public License

  along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/

/***

 * Gap analysis support code for paranoia

 *

 ***/

#ifdef HAVE_CONFIG_H

# include "config.h"

# define __CDIO_CONFIG_H__ 1

#endif

#include "p_block.h"

#include <cdio/paranoia/paranoia.h>

#include "gap.h"

#include <string.h>

/**** Gap analysis code ***************************************************/

/* ===========================================================================

 * i_paranoia_overlap_r (internal)

 *

 * This function seeks backward through two vectors (starting at the given

 * offsets) to determine how many consecutive samples agree.  It returns

 * the number of matching samples, which may be 0.

 *

 * Unlike its sibling, i_paranoia_overlap_f, this function doesn't need to

 * be given the size of the vectors (all vectors stop at offset 0).

 *

 * This function is used by i_analyze_rift_r() below to find where a

 * leading rift ends.

 */

long int

i_paranoia_overlap_r(int16_t *buffA,int16_t *buffB,

			  long offsetA, long offsetB)

{

  long beginA=offsetA;

  long beginB=offsetB;

  /* Start at the given offsets and work our way backwards until we hit

   * the beginning of one of the vectors.

   */

  for( ; beginA>=0 && beginB>=0; beginA--,beginB-- )

    if (buffA[beginA] != buffB[beginB]) break;

  return(offsetA-beginA);

}

/* ===========================================================================

 * i_paranoia_overlap_f (internal)

 *

 * This function seeks forward through two vectors (starting at the given

 * offsets) to determine how many consecutive samples agree.  It returns

 * the number of matching samples, which may be 0.

 *

 * Unlike its sibling, i_paranoia_overlap_r, this function needs to given

 * the size of the vectors.

 *

 * This function is used by i_analyze_rift_f() below to find where a

 * trailing rift ends.

 */

long int 

i_paranoia_overlap_f(int16_t *buffA,int16_t *buffB,

		     long offsetA, long offsetB,

		     long sizeA,long sizeB)

{

  long endA=offsetA;

  long endB=offsetB;

  /* Start at the given offsets and work our way forward until we hit

   * the end of one of the vectors.

   */

  for(;endA

    if(buffA[endA]!=buffB[endB])break;

  return(endA-offsetA);

}

/* ===========================================================================

 * i_stutter_or_gap (internal)

 *

 * This function compares (gap) samples of two vectors at the given offsets.

 * It returns 0 if all the samples are identical, or nonzero if they differ.

 *

 * This is used by i_analyze_rift_[rf] below to determine whether a rift

 * contains samples dropped by the other vector (that should be inserted),

 * or whether the rift contains a stutter (that should be dropped).  See

 * i_analyze_rift_[rf] for more details.

 */

int 

i_stutter_or_gap(int16_t *A, int16_t *B,long offA, long offB, long int gap)

{

  long a1=offA;

  long b1=offB;

  /* If the rift was so big that there aren't enough samples in the other

   * vector to compare against the full gap, then just compare what we

   * have available.  E.g.:

   *

   *            (5678)|(newly matching run ...)

   *    (... 12345678)| (345678) |(newly matching run ...)

   *

   * In this case, a1 would be -2, since we'd want to compare 6 samples

   * against a vector that had only 4.  So we start 2 samples later, and

   * compare the 4 available samples.

   *

   * Again, this approach to identifying stutters is simply a heuristic,

   * so this may not produce correct results in all cases.

   */

  if(a1<0){

    /* Note that a1 is negative, so we're increasing b1 and decreasing (gap).

     */

    b1-=a1;

    gap+=a1;

    a1=0;

  }

  /* Note that we don't have an equivalent adjustment for leading rifts.

   * Thus, it's possible for the following memcmp() to run off the end

   * of A.  See the bug note in i_analyze_rift_r().

   */

  /* Multiply gap by 2 because samples are 2 bytes long and memcmp compares

   * at the byte level.

   */

  return(memcmp(A+a1,B+b1,gap*2));

}

/* riftv is the first value into the rift -> or <- */

/* ===========================================================================

 * i_analyze_rift_f (internal)

 *

 * This function examines a trailing rift to see how far forward the rift goes

 * and to determine what kind of rift it is.  This function is called by

 * i_stage2_each() when a trailing rift is detected.  (aoffset,boffset) are

 * the offsets into (A,B) of the first mismatching sample.

 *

 * This function returns:

 *  matchA  > 0 if there are (matchA) samples missing from A

 *  matchA  < 0 if there are (-matchA) duplicate samples (stuttering) in A

 *  matchB  > 0 if there are (matchB) samples missing from B

 *  matchB  < 0 if there are (-matchB) duplicate samples in B

 *  matchC != 0 if there are (matchC) samples of garbage, after which

 *              both A and B are in sync again

 */

void 

i_analyze_rift_f(int16_t *A,int16_t *B,

		 long sizeA, long sizeB,

		 long aoffset, long boffset, 

		 long *matchA,long *matchB,long *matchC)

{

  long apast=sizeA-aoffset;

  long bpast=sizeB-boffset;

  long i;

  *matchA=0, *matchB=0, *matchC=0;

  /* Look forward to see where we regain agreement between vectors

   * A and B (of at least MIN_WORDS_RIFT samples).  We look for one of

   * the following possible matches:

   * 

   *                         edge

   *                          v

   * (1)  (... A matching run)|(aoffset matches ...)

   *      (... B matching run)| (rift) |(boffset+i matches ...)

   *

   * (2)  (... A matching run)| (rift) |(aoffset+i matches ...)

   *      (... B matching run)|(boffset matches ...)

   *

   * (3)  (... A matching run)| (rift) |(aoffset+i matches ...)

   *      (... B matching run)| (rift) |(boffset+i matches ...)

   *

   * Anything that doesn't match one of these three is too corrupt to

   * for us to recover from.  E.g.:

   *

   *      (... A matching run)| (rift) |(eventual match ...)

   *      (... B matching run)| (big rift) |(eventual match ...)

   *

   * We won't find the eventual match, since we wouldn't be sure how

   * to fix the rift.

   */

  for(i=1;;i++){

    /* Search for whatever case we hit first, so as to end up with the

     * smallest rift.

     */

    /* Don't search for (1) past the end of B */

    if (i

      /* See if we match case (1) above, which either means that A dropped

       * samples at the rift, or that B stuttered.

       */

      if(i_paranoia_overlap_f(A,B,aoffset,boffset+i,sizeA,sizeB)>=MIN_WORDS_RIFT){

	*matchA=i;

	break;

      }

    /* Don't search for (2) or (3) past the end of A */

    if (i

      /* See if we match case (2) above, which either means that B dropped

       * samples at the rift, or that A stuttered.

       */

      if(i_paranoia_overlap_f(A,B,aoffset+i,boffset,sizeA,sizeB)>=MIN_WORDS_RIFT){

	*matchB=i;

	break;

      }

      /* Don't search for (3) past the end of B */

      if (i

        /* See if we match case (3) above, which means that a fixed-length

         * rift of samples is getting read unreliably.

         */

	if(i_paranoia_overlap_f(A,B,aoffset+i,boffset+i,sizeA,sizeB)>=MIN_WORDS_RIFT){

	  *matchC=i;

	  break;

	}

    }else

      /* Stop searching when we've reached the end of both vectors.

       * In theory we could stop when there aren't MIN_WORDS_RIFT samples

       * left in both vectors, but this case should happen fairly rarely.

       */

      if(i>=bpast)break;

    /* Try the search again with a larger tentative rift. */

  }

  if(*matchA==0 && *matchB==0 && *matchC==0)return;

  if(*matchC)return;

  /* For case (1) or (2), we need to determine whether the rift contains

   * samples dropped by the other vector (that should be inserted), or

   * whether the rift contains a stutter (that should be dropped).  To

   * distinguish, we check the contents of the rift against the good samples

   * just before the rift.  If the contents match, then the rift contains

   * a stutter.

   *

   * A stutter in the second vector:

   *     (...good samples... 1234)|(567 ...newly matched run...)

   *     (...good samples... 1234)| (1234) | (567 ...newly matched run)

   *

   * Samples missing from the first vector:

   *     (...good samples... 1234)|(901 ...newly matched run...)

   *     (...good samples... 1234)| (5678) |(901 ...newly matched run...)

   *

   * Of course, there's no theoretical guarantee that a non-stutter

   * truly represents missing samples, but given that we're dealing with

   * verified fragments in stage 2, we can have some confidence that this

   * is the case.

   */

  if(*matchA){

    /* For case (1), we need to determine whether A dropped samples at the

     * rift or whether B stuttered.

     *

     * If the rift doesn't match the good samples in A (and hence in B),

     * it's not a stutter, and the rift should be inserted into A.

     */

    if(i_stutter_or_gap(A,B,aoffset-*matchA,boffset,*matchA))

      return;

    /* It is a stutter, so we need to signal that we need to remove

     * (matchA) bytes from B.

     */

    *matchB = -*matchA;

    *matchA=0;

    return;

  }else{

    /* Case (2) is the inverse of case (1) above. */

    if(i_stutter_or_gap(B,A,boffset-*matchB,aoffset,*matchB))

      return;

    *matchA = -*matchB;

    *matchB=0;

    return;

  }

}

/* riftv must be first even val of rift moving back */

/* ===========================================================================

 * i_analyze_rift_r (internal)

 *

 * This function examines a leading rift to see how far back the rift goes

 * and to determine what kind of rift it is.  This function is called by

 * i_stage2_each() when a leading rift is detected.  (aoffset,boffset) are

 * the offsets into (A,B) of the first mismatching sample.

 *

 * This function returns:

 *  matchA  > 0 if there are (matchA) samples missing from A

 *  matchA  < 0 if there are (-matchA) duplicate samples (stuttering) in A

 *  matchB  > 0 if there are (matchB) samples missing from B

 *  matchB  < 0 if there are (-matchB) duplicate samples in B

 *  matchC != 0 if there are (matchC) samples of garbage, after which

 *              both A and B are in sync again

 */

void 

i_analyze_rift_r(int16_t *A,int16_t *B,

		 long sizeA, long sizeB,

		 long aoffset, long boffset, 

		 long *matchA,long *matchB,long *matchC)

{

  long apast=aoffset+1;

  long bpast=boffset+1;

  long i;

  *matchA=0, *matchB=0, *matchC=0;

  /* Look backward to see where we regain agreement between vectors

   * A and B (of at least MIN_WORDS_RIFT samples).  We look for one of

   * the following possible matches:

   * 

   *                                    edge

   *                                      v

   * (1)             (... aoffset matches)|(A matching run ...)

   *      (... boffset-i matches)| (rift) |(B matching run ...)

   *

   * (2)  (... aoffset-i matches)| (rift) |(A matching run ...)

   *                (... boffset matches)|(B matching run ...)

   *

   * (3)  (... aoffset-i matches)| (rift) |(A matching run ...)

   *      (... boffset-i matches)| (rift) |(B matching run ...)

   *

   * Anything that doesn't match one of these three is too corrupt to

   * for us to recover from.  E.g.:

   *

   *         (... eventual match)| (rift) |(A matching run ...)

   *    (... eventual match) | (big rift) |(B matching run ...)

   *

   * We won't find the eventual match, since we wouldn't be sure how

   * to fix the rift.

   */

  for(i=1;;i++){

    /* Search for whatever case we hit first, so as to end up with the

     * smallest rift.

     */

    /* Don't search for (1) past the beginning of B */

    if (i

      /* See if we match case (1) above, which either means that A dropped

       * samples at the rift, or that B stuttered.

       */

      if(i_paranoia_overlap_r(A,B,aoffset,boffset-i)>=MIN_WORDS_RIFT){

	*matchA=i;

	break;

      }

    /* Don't search for (2) or (3) past the beginning of A */

    if (i

      /* See if we match case (2) above, which either means that B dropped

       * samples at the rift, or that A stuttered.

       */

      if(i_paranoia_overlap_r(A,B,aoffset-i,boffset)>=MIN_WORDS_RIFT){

	*matchB=i;

	break;

      }

      /* Don't search for (3) past the beginning of B */

      if (i

	/* See if we match case (3) above, which means that a fixed-length

	 * rift of samples is getting read unreliably.

	 */

	if(i_paranoia_overlap_r(A,B,aoffset-i,boffset-i)>=MIN_WORDS_RIFT){

	  *matchC=i;

	  break;

	}

    }else

      /* Stop searching when we've reached the end of both vectors.

       * In theory we could stop when there aren't MIN_WORDS_RIFT samples

       * left in both vectors, but this case should happen fairly rarely.

       */

      if(i>=bpast)break;

    /* Try the search again with a larger tentative rift. */

  }

  if(*matchA==0 && *matchB==0 && *matchC==0)return;

  if(*matchC)return;

  /* For case (1) or (2), we need to determine whether the rift contains

   * samples dropped by the other vector (that should be inserted), or

   * whether the rift contains a stutter (that should be dropped).  To

   * distinguish, we check the contents of the rift against the good samples

   * just after the rift.  If the contents match, then the rift contains

   * a stutter.

   *

   * A stutter in the second vector:

   *              (...newly matched run... 234)|(5678 ...good samples...)

   *     (...newly matched run... 234)| (5678) |(5678 ...good samples...)

   *

   * Samples missing from the first vector:

   *              (...newly matched run... 890)|(5678 ...good samples...)

   *     (...newly matched run... 890)| (1234) |(5678 ...good samples...)

   *

   * Of course, there's no theoretical guarantee that a non-stutter

   * truly represents missing samples, but given that we're dealing with

   * verified fragments in stage 2, we can have some confidence that this

   * is the case.

   */

  if(*matchA){

    /* For case (1), we need to determine whether A dropped samples at the

     * rift or whether B stuttered.

     *

     * If the rift doesn't match the good samples in A (and hence in B),

     * it's not a stutter, and the rift should be inserted into A.

     *

     * ???BUG??? It's possible for aoffset+1+*matchA to be > sizeA, in

     * which case the comparison in i_stutter_or_gap() will extend beyond

     * the bounds of A.  Thankfully, this isn't writing data and thus

     * trampling memory, but it's still a memory access error that should

     * be fixed.

     *

     * This bug is not fixed yet.

     */

    if(i_stutter_or_gap(A,B,aoffset+1,boffset-*matchA+1,*matchA))

      return;

    /* It is a stutter, so we need to signal that we need to remove

     * (matchA) bytes from B.

     */

    *matchB = -*matchA;

    *matchA=0;

    return;

  }else{

    /* Case (2) is the inverse of case (1) above. */

    if(i_stutter_or_gap(B,A,boffset+1,aoffset-*matchB+1,*matchB))

      return;

    *matchA = -*matchB;

    *matchB=0;

    return;

  }

}

/* ===========================================================================

 * analyze_rift_silence_f (internal)

 *

 * This function examines the fragment and root from the rift onward to

 * see if they have a rift's worth of silence (or if they end with silence).

 * It sets (*matchA) to -1 if A's rift is silence, (*matchB) to -1 if B's

 * rift is silence, and sets them to 0 otherwise.

 *

 * Note that, unlike every other function in cdparanoia, this function

 * considers any repeated value to be silence (which, in effect, it is).

 * All other functions only consider repeated zeroes to be silence.

 *

 * ??? Is this function name just a misnomer, as it's really looking for

 * repeated garbage?

 *

 * This function is called by i_stage2_each() if it runs into a trailing rift

 * that i_analyze_rift_f couldn't diagnose.  This checks for another variant:

 * where one vector has silence and the other doesn't.  We then assume

 * that the silence (and anything following it) is garbage.

 *

 * Note that while this function checks both A and B for silence, the caller

 * assumes that only one or the other has silence.

 */

void

analyze_rift_silence_f(int16_t *A,int16_t *B,long sizeA,long sizeB,

		       long aoffset, long boffset,

		       long *matchA, long *matchB)

{

  *matchA=-1;

  *matchB=-1;

  /* Search for MIN_WORDS_RIFT samples, or to the end of the vector,

   * whichever comes first.

   */

  sizeA=min(sizeA,aoffset+MIN_WORDS_RIFT);

  sizeB=min(sizeB,boffset+MIN_WORDS_RIFT);

  aoffset++;

  boffset++;

  /* Check whether A has only "silence" within the search range.  Note

   * that "silence" here is a single, repeated value (zero or not).

   */

  while(aoffset

    if(A[aoffset]!=A[aoffset-1]){

      *matchA=0;

      break;

    }

    aoffset++;

  }

  /* Check whether B has only "silence" within the search range.  Note

   * that "silence" here is a single, repeated value (zero or not).

   *

   * Also note that while the caller assumes that only matchA or matchB

   * is set, we check both vectors here.

   */

  while(boffset

    if(B[boffset]!=B[boffset-1]){

      *matchB=0;

      break;

    }

    boffset++;

  }

}