/*

 * 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 {

		} 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")

}

	if myLog.verbosity < 4 {

		return

	}

	for _, sc := range data.sizeGroups {

		c1 += len(sc.files)

	}

	}

}

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

	for _, sizeGroup := range data.sizeGroups {

		for _, l := range sizeGroup.fullsums {

			hgroups = append(hgroups, l)

		}

	}

	return

}

			continue

		}

	}

			continue

		}

	}

}

		}

	}

		}

}

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

}

// initialCleanup() removes files with unique size as well as hard links

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

	for s, sizeGroup := range data.sizeGroups {

		if len(sizeGroup.files) < 2 {

			delete(data.sizeGroups, s)

			uniqueSizeCount++

			continue

		}

		var hardlinksFound bool

		// Check for hardlinks

		// Remove unique dev/inodes

		// Instead of this loop, another way would be to use the field

		// "Unique" of the fileObj to mark them to be discarded

		// and remove them all at the end.

		for {

			if !OSHasInodes() {

				break

			}

			var hardLinkIndex int

			fo := sizeGroup.files[0]

			prevDev, prevIno := GetDevIno(fo)

			for i, fo := range sizeGroup.files[1:] {

				dev, ino := GetDevIno(fo)

				if dev == prevDev && ino == prevIno {

					hardLinkIndex = i + 1

					hardLinkCount++

					hardlinksFound = true

					break

				}

				prevDev = dev

				prevIno = ino

			}

			if hardLinkIndex == 0 {

				break

			}

			i := hardLinkIndex

			// Remove hardink

			copy(sizeGroup.files[i:], sizeGroup.files[i+1:])

			sizeGroup.files[len(sizeGroup.files)-1] = nil

			sizeGroup.files = sizeGroup.files[:len(sizeGroup.files)-1]

		}

		// We have found hard links in this size group,

		// maybe we can remove it

		if hardlinksFound {

			if len(sizeGroup.files) < 2 {

				delete(data.sizeGroups, s)

				uniqueSizeCount++

				continue

			}

		}

	}

	return

}

func formatSize(sizeBytes uint64, short bool) string {

	var units = map[int]string{

		0: "B",

		1: "KiB",

		2: "MiB",

		3: "GiB",

		4: "TiB",

		5: "PiB",

	}

	humanSize := sizeBytes

	var n int

	for n < len(units)-1 {

		if humanSize < 10000 {

			break

		}

		humanSize /= 1024

		n++

	}

	if n < 1 {