/*

 * Copyright (C) 2014 Mikael Berthe <mikael@lilotux.net>

 *

 * 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 2 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, write to the Free Software

 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307

 * USA

 */

// This program (Goduf) is a fast duplicate file finder.

// Use goduf --help to get the list of available options.

package main

import (

	"crypto/sha1"

	"encoding/hex"

	"errors"

	"flag"

	"fmt"

	"io"

	"log"

	"os"

	"path/filepath"

	"sort"

)

const medsumBytes = 128

const minSizePartialChecksum = 49152 // Should be > 3*medsumBytes

type sumType int

const (

	fullChecksum sumType = iota

	partialChecksum

)

type fileObj struct {

	//Unique   bool

	FilePath string

	os.FileInfo

	PartialHash []byte

	Hash        []byte

}

type FileObjList []*fileObj

type sizeClass struct {

	files    FileObjList

	medsums  map[string]FileObjList

	fullsums map[string]FileObjList

}

type dataT struct {

	totalSize   uint64

	cmpt        uint

	sizeGroups  map[int64]*sizeClass

	emptyFiles  FileObjList

	ignoreCount int

}

var data dataT

type myLogT struct {

	verbosity int

}

var myLog myLogT

func (l *myLogT) Printf(level int, format string, args ...interface{}) {

	if level > l.verbosity {

		return

	}

	if level >= 0 {

		log.Printf(format, args...)

		return

	}

	// Error message without timestamp

	fmt.Fprintf(os.Stderr, format, args...)

}

func (l *myLogT) Println(level int, args ...interface{}) {

	if level > l.verbosity {

		return

	}

	if level >= 0 {

		log.Println(args...)

		return

	}

	// Error message without timestamp

	fmt.Fprintln(os.Stderr, args...)

}

func visit(path string, f os.FileInfo, err error) error {

	if err != nil {

		if f == nil {

			return err

		}

		if f.IsDir() {

			myLog.Println(-1, "Warning: cannot process directory:",

				path)

			return filepath.SkipDir

		}

		myLog.Println(-1, "Ignoring ", path, " - ", err)

		data.ignoreCount++

		return nil

	}

	if f.IsDir() {

		return nil

	}

	if mode := f.Mode(); mode&os.ModeType != 0 {

		if mode&os.ModeSymlink != 0 {

			myLog.Println(5, "Ignoring symbolic link", path)

		} else {

			myLog.Println(0, "Ignoring special file", path)

		}

		data.ignoreCount++

		return nil

	}

	data.cmpt++

	data.totalSize += uint64(f.Size())

	fo := &fileObj{FilePath: path, FileInfo: f}

	if _, ok := data.sizeGroups[f.Size()]; !ok {

		data.sizeGroups[f.Size()] = &sizeClass{}

	}

	data.sizeGroups[f.Size()].files =

		append(data.sizeGroups[f.Size()].files, fo)

	return nil

}

func (fo *fileObj) CheckSum() error {

	file, err := os.Open(fo.FilePath)

	if err != nil {

		return err

	}

	defer file.Close()

	hash := sha1.New()

	if size, err := io.Copy(hash, file); size != fo.Size() || err != nil {

		if err == nil {

			return errors.New("failed to read the whole file: " +

				fo.FilePath)

		}

		return err

	}

	fo.Hash = hash.Sum(nil)

	return nil

}

func (fo *fileObj) MedSum() error {

	file, err := os.Open(fo.FilePath)

	if err != nil {

		return err

	}

	defer file.Close()

	hash := sha1.New()

	// XXX: duplicated code!

	// BOF

	if _, err := io.CopyN(hash, file, medsumBytes); err != nil {

		if err == nil {

			return errors.New("failed to read bytes from file:" +

				fo.FilePath)

		}

		return err

	}

	/*

		// MOF

		file.Seek((fo.Size()-medsumBytes)/2, 0)

		if _, err := io.CopyN(hash, file, medsumBytes); err != nil {

			if err == nil {

				return errors.New("failed to read bytes from file:" +

					fo.FilePath)

			}

			return err

		}

	*/

	// EOF

	file.Seek(0-medsumBytes, 2)

	if _, err := io.CopyN(hash, file, medsumBytes); err != nil {

		if err == nil {

			return errors.New("failed to read bytes from file:" +

				fo.FilePath)

		}

		return err

	}

	fo.PartialHash = hash.Sum(nil)

	return nil

}

func (fo *fileObj) Sum(sType sumType) error {

	if sType == partialChecksum {

		return fo.MedSum()

	} else if sType == fullChecksum {

		return fo.CheckSum()

	}

	panic("Internal error: Invalid sType")

}

func (data *dataT) dispCount() {

	if myLog.verbosity < 4 {

		return

	}

	var c1, c2, c3, c4 int

	var s4 string

	for _, sc := range data.sizeGroups {

		c1 += len(sc.files)

		for _, fol := range sc.medsums {

			c2 += len(fol)

		}

		for _, fol := range sc.fullsums {

			c3 += len(fol)

		}

	}

	c4 = len(data.emptyFiles)

	if c4 > 0 {

		s4 = fmt.Sprintf("+%d", c4)

	}

	myLog.Printf(4, "  Current countdown: %d  [%d%s/%d/%d]\n",

		c1+c2+c3+c4, c1, s4, c2, c3)

}

func (data *dataT) filesWithSameHash() (hgroups []FileObjList) {

	for _, sizeGroup := range data.sizeGroups {

		for _, l := range sizeGroup.fullsums {

			hgroups = append(hgroups, l)

		}

	}

	return

}

func createHashFromSum(sType sumType, folist FileObjList, hashes *map[string]FileObjList) {

	for _, fo := range folist {

		var hash string

		var hbytes []byte

		if sType == partialChecksum {

			hbytes = fo.PartialHash

		} else if sType == fullChecksum {

			hbytes = fo.Hash

		} else {

			panic("Internal error: Invalid sType")

		}

		if hbytes == nil {

			// Could happen if the file was not readable,

			// We skip it (already shown as dropped)

			continue

		}

		hash = hex.EncodeToString(hbytes)

		(*hashes)[hash] = append((*hashes)[hash], fo)

	}

}

func (data *dataT) calculateMedSums() {

	var bigList FileObjList

	var droppedGroups int

	var droppedFiles int

	// Create a unique list of files to be partially checksummed

	for size, sizeGroup := range data.sizeGroups {

		if size < minSizePartialChecksum {

			// We do not use MedSums for small files

			continue

		}

		bigList = append(bigList, sizeGroup.files...)

	}

	// Sort the list for better efficiency -- that's the whole point of

	// the unique big list.

	sort.Sort(ByInode(bigList))

	// Compute partial checksums

	for _, fo := range bigList {

		if err := fo.Sum(partialChecksum); err != nil {

			myLog.Println(0, "Error:", err)

			droppedFiles++

			// The hash part will be nil and the file will

			// be dropped in createHashFromSum() below.

		}

	}

	// Reparse size-grouped hashes and use the new hash information

	// to build lists of files with the same partial checksum.

	for size, sizeGroup := range data.sizeGroups {

		if size < minSizePartialChecksum {

			// We do not use MedSums for small files

			continue

		}

		hashes := make(map[string]FileObjList)

		createHashFromSum(partialChecksum, sizeGroup.files, &hashes)

		// Let's de-dupe now...

		for h, l := range hashes {

			if len(l) < 2 {

				droppedGroups++

				droppedFiles += len(l)

				delete(hashes, h)

			}

		}

		// Done, save the result

		data.sizeGroups[size].medsums = hashes

		// We remove the items from "files" since they are in the hash

		// tree now.

		sizeGroup.files = nil

		if len(hashes) == 0 { // We're done with this size group

			delete(data.sizeGroups, size)

		}

	}

	if droppedFiles > 0 {

		myLog.Printf(3, "  Dropped %d files in %d groups\n",

			droppedFiles, droppedGroups)

	}

	return

}

func (data *dataT) calculateChecksums() {

	var bigList FileObjList

	var droppedGroups int

	var droppedFiles int

	// Create a unique list of files to be fully checksummed

	for _, sizeGroup := range data.sizeGroups {

		// #1: small files

		bigList = append(bigList, sizeGroup.files...)

		// #2: files with same partial checksum

		for _, l := range sizeGroup.medsums {

			bigList = append(bigList, l...)

		}

	}

	// Sort the list for better efficiency -- that's the whole point of

	// the unique big list.

	sort.Sort(ByInode(bigList))

	// Compute full checksums

	for _, fo := range bigList {

		if err := fo.Sum(fullChecksum); err != nil {

			myLog.Println(0, "Error:", err)

			droppedFiles++

			// The hash part will be nil and the file will

			// be dropped in createHashFromSum() below.

		}

	}

	// Reparse size-grouped hashes and use the new hash information

	// to build lists of files with the same checksum.

	for size, sizeGroup := range data.sizeGroups {

		hashes := make(map[string]FileObjList)

		// #1: small files

		createHashFromSum(fullChecksum, sizeGroup.files, &hashes)

		// #2: files with same partial checksum

		for _, l := range sizeGroup.medsums {

			createHashFromSum(fullChecksum, l, &hashes)

		}

		// Let's de-dupe now...

		for h, l := range hashes {

			if len(l) < 2 {

				droppedGroups++

				droppedFiles += len(l)

				delete(hashes, h)

			}

		}

		// Done, save the result

		data.sizeGroups[size].fullsums = hashes

		data.sizeGroups[size].medsums = nil

		sizeGroup.files = nil

	}

	if droppedFiles > 0 {

		myLog.Printf(3, "  Dropped %d files in %d groups\n",

			droppedFiles, droppedGroups)

	}

	return

}

func (data *dataT) dropEmptyFiles(ignoreEmpty bool) (emptyCount int) {

	sc, ok := data.sizeGroups[0]

	if ok == false {

		return // no empty files

	}

	if !ignoreEmpty {

		if len(sc.files) > 1 {

			data.emptyFiles = sc.files

		}

		delete(data.sizeGroups, 0)

		return

	}

	emptyCount = len(sc.files)

	delete(data.sizeGroups, 0)

	return

}

func (data *dataT) createSizeHash() (hardLinkCount, uniqueSizeCount int) {

	for s, sizeGroup := range data.sizeGroups {

		if len(sizeGroup.files) < 2 {

			delete(data.sizeGroups, s)

			uniqueSizeCount++

			continue

		}