fdmffingerprint.java

dump3 morpheus 0.2.9 src

/**
 * DuMP3 version morpheus_0.2.9 - a duplicate/similar file finder in Java<BR>
 * Copyright 2005 Alexander Gr&auml;sser<BR>
 * All Rights Reserved, http://dump3.sourceforge.net/<BR>
 * <BR>
 * This file is part of DuMP3.<BR>
 * <BR>
 * DuMP3 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 2 of the License, or (at your option) any later version.<BR>
 * <BR>
 * DuMP3 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.<BR>
 * <BR>
 * You should have received a copy of the GNU General Public License along with DuMP3; if not, write to the Free Software Foundation, Inc., 51 Franklin St,
 * Fifth Floor, Boston, MA 02110-1301 USA
 */
package net.za.grasser.duplicate.fingerprint;

import java.awt.Point;
import java.io.File;
import java.io.InputStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import javax.sound.sampled.AudioFileFormat;
import javax.sound.sampled.AudioFormat;
import javax.sound.sampled.AudioInputStream;
import javax.sound.sampled.AudioSystem;
import javax.sound.sampled.DataLine;
import javax.sound.sampled.SourceDataLine;
import javax.sound.sampled.AudioFormat.Encoding;
import javax.sound.sampled.spi.FormatConversionProvider;
import net.za.grasser.duplicate.Configure;
import net.za.grasser.duplicate.file.FingerprintFile;
import net.za.grasser.duplicate.file.Status;
import net.za.grasser.duplicate.fingerprint.configure.ConfigFactory;
import net.za.grasser.duplicate.fingerprint.configure.FdmfFingerprintConfig;
import net.za.grasser.duplicate.util.fft.Complex;
import net.za.grasser.duplicate.util.fft.FFT;
import org.apache.log4j.Logger;
import com.sun.media.sound.JDK13Services;

/**
 * REF: <a href="http://www.w140.com/audio/">fdmf</a>Thomas Jarosch, Aug 2004
 * 
 * @author <a href="http://sourceforge.net/sendmessage.php?touser=733840">pyropunk at sourceforge dot net</a>
 * @version $Revision: 1.15 $
 * @modelguid {87AC7397-9A44-4C1C-B351-255DFA8ACEA3}
 */
public class FdmfFingerprint extends AbstractFingerprint {
  /**
   * <code>log</code> FdmfFingerprint -
   */
  private static final Logger log = Logger.getLogger(FdmfFingerprint.class);
  static {
    Configure.load();
    final Set<String> set = new HashSet<String>();
    final Iterator<FormatConversionProvider> it = JDK13Services.getProviders(FormatConversionProvider.class).iterator();
    while (it.hasNext()) {
      final FormatConversionProvider fcp = it.next();
      final Encoding[] as = fcp.getSourceEncodings();
      for (final Encoding element : as) {
        set.add(element.toString());
      }
    }
    if (log.isInfoEnabled()) {
      final StringBuffer s = new StringBuffer(100);
      s.append("[");
      final Iterator<String> it2 = set.iterator();
      if (it2.hasNext()) {
        s.append(it2.next());
      }
      while (it2.hasNext()) {
        s.append(", ").append(it2.next());
      }
      s.append(']');
      log.info("Supported file formats:" + s);
    }
  }
  /**
   * <code>WINDOW_RECTANGULAR</code> FdmfFingerprint -
   */
  public static final int WINDOW_RECTANGULAR = 0;
  /**
   * <code>WINDOW_HANNING</code> FdmfFingerprint -
   */
  public static final int WINDOW_HANNING = 1;
  /**
   * <code>WINDOW_HAMMING</code> FdmfFingerprint -
   */
  public static final int WINDOW_HAMMING = 2;
  /**
   * <code>WINDOW_RAISED_COSINE</code> FdmfFingerprint -
   */
  public static final int WINDOW_RAISED_COSINE = 3;
  /**
   * <code>WINDOW_WELCH</code> FdmfFingerprint -
   */
  public static final int WINDOW_WELCH = 4;
  /**
   * <code>WINDOW_BARTLETT</code> FdmfFingerprint -
   */
  public static final int WINDOW_BARTLETT = 5;
  /**
   * <code>WINDOW_KAISER</code> FdmfFingerprint -
   */
  public static final int WINDOW_KAISER = 6;
  /**
   * <code>CHUNK_SAMPLES</code> FdmfFingerprint - approx. 375 milliseconds
   */
  public static final int CHUNK_SAMPLES = 16384;
  /**
   * <code>MAXCHUNKS</code> FdmfFingerprint - (65536 = 6.7 hours) (256 = 1.58 min) at 371 ms per chunk
   */
  private static final int MAX_CHUNKS = 256;
  /**
   * <code>NUM_BANDS</code> FdmfFingerprint - number of frequency bands to analyse
   */
  private static final int NUM_BANDS = 4;
  /**
   * <code>frequency</code> FdmfFingerprint -
   */
  private static final int[] frequency = {
      3, 15, 90, 600, 5000
  };
  /**
   * <code>config</code> FdmfFingerprint -
   */
  private static final FdmfFingerprintConfig config = (FdmfFingerprintConfig)ConfigFactory.getConfig(FdmfFingerprint.class);

  /**
   * compare the bit counts of two byte arrays
   * 
   * @param a
   * @param b
   * @return percentage of matching bits
   */
  private static double compare(final byte[] a, final byte[] b) {
    final double lena = a.length / 3;
    final double lenb = b.length / 3;
    final double len = Math.min(lena, lenb);
    double match = 0.0;
    for (int j = 0; j < 3; j++) {
      for (int i = 0; i < len; i++) {
        final BigInteger x = new BigInteger(("" + (a[(j * (int)lena + i)] & 0xff ^ b[(j * (int)lenb + i)] & 0xff ^ 0xff)));
        match += x.bitCount();
      }
    }
    return match / (len * 24.0) * 100.0;
  }

  /**
   * @param pList
   * @return median fo the list
   */
  private static double median(final List<Double> pList) {
    final int length = pList.size();
    final List<Double> clone = new ArrayList<Double>(pList);
    Collections.sort(clone);
    if (length % 2 == 0) {
      // even - median = average of two middle values
      return (clone.get((length >> 1)).doubleValue() + clone.get((length - 2 >> 1)).doubleValue()) / 2.0;
    }
    // odd - median = middle value
    return clone.get((length - 1 >> 1)).doubleValue();
  }

  /**
   * one bit quantize with median value as threshold
   * 
   * @param pArray
   * @return quantized byte array
   */
  private static byte[] quantize(final Complex[] pArray) {
    final List<Double> list = new ArrayList<Double>(pArray.length);
    for (final Complex element : pArray) {
      list.add(new Double(element.abs()));
    }
    final double median = median(list);
    final byte[] ba = new byte[list.size() >> 3];
    final Iterator<Double> it = list.iterator();
    int i = 7;
    int j = 0;
    ba[0] = 0;
    while (it.hasNext()) {
      final double d = it.next().doubleValue();
      if (d > median) {
        ba[j] |= 1 << i;
      }
      if (i <= 0) {
        j++;
        i = 7;
        if (it.hasNext()) {
          ba[j] = 0;
        }
      } else {
        i--;
      }
    }
    return ba;
  }

  /**
   * <code>started</code> FdmfFingerprint - used to ignore starting silence
   */
  boolean started = true;
  /**
   * <code>fftPos</code> FdmfFingerprint - position in fft array
   */
  int fftPos = 0;
  /**
   * <code>fftInputArray</code> FdmfFingerprint - array of input values for the FFT
   */
  Complex[] fftInputArray = null;
  /**
   * <code>chunkPos</code> FdmfFingerprint -
   */
  int chunkPos = 0;
  /**
   * <code>energyBuffer</code> FdmfFingerprint -
   */
  Complex[] energyBuffer = null;
  /**
   * <code>ratioBuffer</code> FdmfFingerprint -
   */
  Complex[] ratioBuffer = null;
  /**
   * <code>twistBuffer</code> FdmfFingerprint -
   */
  Complex[] twistBuffer = null;

  /**
   * @param fi FingerprintFile
   * @modelguid {53F63DBA-703A-4B81-882B-F1B4318D5CC9}
   */
  public FdmfFingerprint(final FingerprintFile fi) {
    super(fi);
  }

  /**
   * This method adds additional info to the FingerprintFile
   */
  @Override
  public void addInfo() {
    super.addInfo();
    try {
      final Map<String, String> map = getFile().getInfo();
      final File file = new File(getFile().getPath());
      // AudioFileFormat properties
      final AudioFileFormat baseFileFormat = AudioSystem.getAudioFileFormat(file);
      map.put("format", AudioSystem.getAudioInputStream(file).getFormat().toString());
      Map<String, Object> properties = baseFileFormat.properties();
      if (properties != null) {
        for (final String lString : properties.keySet()) {
          // read InputStreams
          final Object o = properties.get(lString);
          if (o instanceof InputStream) {
            final InputStream tag = (InputStream)o;
            final byte[] buff = new byte[256];
            final StringBuffer sb = new StringBuffer();
            int len = tag.read(buff);
            while (len > 0) {
              sb.append(new String(buff, 0, len));
              len = tag.read(buff);
            }
          } else {
            // otherwise convert to String
            map.put(lString, o.toString());
          }
        }
      }
      // AudioFormat properties
      properties = baseFileFormat.getFormat().properties();
      if (properties != null) {
        for (final String lString : properties.keySet()) {
          map.put(lString, properties.get(lString).toString());
        }
      }
    } catch (final Throwable t) {
      log.error("Could not get info", t);
    }
  }

  /**
   * This routine takes in a data structure that is the output of an FFT operation. The input to this routine is in the frequency domain. The power is
   * integrated over NUM_BANDS non-overrlapping frequency bands. These band energies are returned to the caller in an array of double.