use internal functions to speed up, not too effective in reading tho…
[shellsnippets/shellsnippets.git] / mksh / findups
1 #!/bin/mksh
2 # $MirOS: contrib/code/Snippets/findups,v 1.2 2011/01/02 00:15:25 tg Exp $
3 #-
4 # Copyright (c) 2010, 2011
5 #       Thorsten Glaser <tg@mirbsd.org>
6 #
7 # Provided that these terms and disclaimer and all copyright notices
8 # are retained or reproduced in an accompanying document, permission
9 # is granted to deal in this work without restriction, including un-
10 # limited rights to use, publicly perform, distribute, sell, modify,
11 # merge, give away, or sublicence.
12 #
13 # This work is provided "AS IS" and WITHOUT WARRANTY of any kind, to
14 # the utmost extent permitted by applicable law, neither express nor
15 # implied; without malicious intent or gross negligence. In no event
16 # may a licensor, author or contributor be held liable for indirect,
17 # direct, other damage, loss, or other issues arising in any way out
18 # of dealing in the work, even if advised of the possibility of such
19 # damage or existence of a defect, except proven that it results out
20 # of said person's immediate fault when using the work as intended.
21 #-
22 # Find duplicate files occupying separate inodes and output calls to
23 # ln to make them hardlinks of each other. Assumes no pathnames with
24 # newlines are used. Links will be generated in argument order.
25
26 nl='
27 '
28 if stat --help >/dev/null 2>&1; then
29         set -A statcmd stat -c '%s %D %i %n'    # GNU stat
30 else
31         set -A statcmd stat -f '%z %d %i %N'    # BSD stat (or so we assume)
32 fi
33 hashalg='cksum -a md4,sfv,oaat1s'; T=$(print | $hashalg 2>/dev/null)
34 if [[ ${T//$nl} = 8c5b220bf6f482881a90287a64aea15032D7069366DFECC2 ]]; then
35         function hashprint {
36                 print -r -- "${1//$nl} $2"
37         }
38 else
39         function hashprint {
40                 print -r -- "${1%% *} $2"
41         }
42         for hashalg in md5 md5sum false; do
43                 T=$(print | $hashalg 2>/dev/null)
44                 [[ ${T%% *} = 68b329da9893e34099c7d8ad5cb9c940 ]] && break
45         done
46         if [[ $hashalg = false ]]; then
47                 print -u2 Cannot find a suitable cksum, md5 or md5sum.
48                 exit 1
49         fi
50 fi
51
52 if (( !$# )); then
53         print -u2 Please pass a directory or several to scan.
54         exit 1
55 fi
56
57 if ! T=$(mktemp -d /tmp/findups.XXXXXXXXXX); then
58         print -u2 Error: cannot create temporary directory.
59         exit 255
60 fi
61
62 print -nu2 Phase 1/4: prepare: finding...
63 find "$@" -type f >"$T/1"
64 print -nu2 " found, stating..."
65 # if this yields stderr, you have newlines in pathnames, which get skipped
66 tr '\n' '\0' <"$T/1" | xargs -0 "${statcmd[@]}" >"$T/2"
67 print -u2 " done"
68 if [[ ! -s $T/2 ]]; then
69         rm -rf "$T"
70         exit 0
71 fi
72
73 # we have output, for each file, size dev_t inode name
74
75 print -nu2 Phase 2/4: counting...
76 # prepend a hex numerical to keep order
77 typeset -Uui16 -Z11 i=0
78 while IFS= read -r line; do
79         print -r -- "${i#16#} $line"
80         let i++
81 done <"$T/2" >"$T/3"
82 typeset -i10 i total=i
83 print -u2 " done, $total files found"
84
85 # order-id size dev_t inode name
86
87 i=0
88 j=0
89 p=-1
90 # for all files of same size, hash and proceed
91 lastsz=-
92 sort -nk2,2 -nk3,3 -nk4,4 <"$T/3" |&
93 while IFS= read -pr line; do
94         if (( (q = (++i * 100) / total) > p )); then
95                 (( p = q ))
96                 print -nu2 '\r'Phase 3/4: hashing... ${p}%, ${i}/${total}
97         fi
98         oid=${line%% *}
99         line=${line#* }
100         sz=${line%% *}
101         line=${line#* }
102         dev=${line%% *}
103         line=${line#* }
104         ino=${line%% *}
105         nm=${line#* }
106
107         # on first and if sizes differ
108         if [[ $sz != "$lastsz" ]]; then
109                 # queue for use later if another file has same size
110                 lastoid=$oid
111                 lastsz=$sz
112                 lastdev=$dev
113                 lastino=$ino
114                 lastnm=$nm
115                 lastfirst=1
116                 continue
117         fi
118
119         # whether one was queued, process it now, lazily
120         if (( lastfirst )); then
121                 lastmd=$($hashalg <"$lastnm")
122                 hashprint "$lastmd" "$lastoid $lastdev $lastino $lastnm"
123                 let ++j
124                 lastfirst=0
125         fi
126
127         # skip hashing if already hardlinked
128         [[ $lastdev:$lastino = "$dev:$ino" ]] || lastmd=$($hashalg <"$nm")
129
130         # process follow-up file
131         lastoid=$oid
132         lastdev=$dev
133         lastino=$ino
134         lastnm=$nm
135         hashprint "$lastmd" "$lastoid $lastdev $lastino $lastnm"
136         let ++j
137 done >"$T/4"
138 (( total = j ))
139 print -u2 '\r'Phase 3/4: hashing... done, $total files in total hashed
140
141 # hash order dev_t inode name
142
143 i=0
144 j=0
145 p=-1
146 # for all files of same hash, emit hardlink command unless already hardlinked
147 lastmd=-
148 sort <"$T/4" |&
149 while IFS= read -pr line; do
150         if (( (q = (++i * 100) / total) > p )); then
151                 (( p = q ))
152                 print -nu2 '\r'Phase 4/4: generating... ${p}%, ${i}/${total}
153         fi
154         md=${line%% *}
155         line=${line#* }
156         line=${line#* }
157         dev=${line%% *}
158         line=${line#* }
159         ino=${line%% *}
160         nm=${line#* }
161
162         if [[ $lastmd != "$md" || $lastdev != "$dev" ]]; then
163                 # first with my hash, or cannot cross-device hardlink anyway
164                 lastmd=$md
165                 lastdev=$dev
166                 lastino=$ino
167                 lastnm=$nm
168                 continue
169         fi
170
171         # attempt to link, unless already done so
172         [[ $lastino = "$ino" ]] && continue
173         print -r -- ln -f \
174             "'${lastnm//\'/\'\\\'\'}'" "'${nm//\'/\'\\\'\'}'"
175         let j++
176 done
177 print -u2 '\r'Phase 4/4: generating... done, $j files in total linked
178
179 rm -rf "$T"