{"thread":{"id":"3771","subject":"[RFH] xdiff shows trivially redundant diff.","startedAt":"2006-04-02T09:15:42Z","lastAt":"2006-04-04T01:55:43Z","messageCount":17,"participants":["Junio C Hamano","Davide Libenzi","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"18212","messageId":"7v4q1cmj7l.fsf@assigned-by-dhcp.cox.net","threadId":"3771","inReplyTo":null,"subject":"[RFH] xdiff shows trivially redundant diff.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-02T09:15:42Z","receivedAt":"2006-04-02T09:15:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"$ git diff-tree -p 52e8a6^2 52d8a6 -- git-fetch.sh\n\nshows a change that trivially is redundant, like this:\n\n diff --git a/git-fetch.sh b/git-fetch.sh\n index b4325d9..de4f011 100755\n --- a/git-fetch.sh\n +++ b/git-fetch.sh\n @@ -320,7 +320,7 @@ fetch_main () {\n ( : subshell because we muck with IFS\n IFS=\" $LF\"\n (\n - git-fetch-pack $exec $keep \"$remo...\n + git-fetch-pack $exec $keep --thin...\n ) |\n while read sha1 remote_name\n do\n @@ -367,21 +367,26 @@ fetch_main \"$reflist\"\n\n # automated tag following\n case \"$no_tags$tags\" in\n -'')\n - taglist=$(IFS=\" \" &&\n - git-ls-remote $upload_pack --tags \"$remote\" |\n ...\n - done)\n +'')\n + case \"$reflist\" in\n + *:refs/*)\n ...\n\nNotice the first '-' and '+' lines of second hunk are identical?\n\nThere is another interesting thing. This is running diff\nbetween 52e8a6^2 and 52d8a6 blobs, but if I change them slightly\nso that the first hunk is not different, then this anomaly\ndisappears.\n"},{"id":"18224","messageId":"Pine.LNX.4.64.0604021035130.30097@alien.or.mcafeemobile.com","threadId":"3771","inReplyTo":"7v4q1cmj7l.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-04-02T17:35:53Z","receivedAt":"2006-04-02T17:35:53Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Sun, 2 Apr 2006, Junio C Hamano wrote:\n\n> $ git diff-tree -p 52e8a6^2 52d8a6 -- git-fetch.sh\n>\n> shows a change that trivially is redundant, like this:\n>\n> diff --git a/git-fetch.sh b/git-fetch.sh\n> index b4325d9..de4f011 100755\n> --- a/git-fetch.sh\n> +++ b/git-fetch.sh\n> @@ -320,7 +320,7 @@ fetch_main () {\n> ( : subshell because we muck with IFS\n> IFS=\" $LF\"\n> (\n> - git-fetch-pack $exec $keep \"$remo...\n> + git-fetch-pack $exec $keep --thin...\n> ) |\n> while read sha1 remote_name\n> do\n> @@ -367,21 +367,26 @@ fetch_main \"$reflist\"\n>\n> # automated tag following\n> case \"$no_tags$tags\" in\n> -'')\n> - taglist=$(IFS=\" \" &&\n> - git-ls-remote $upload_pack --tags \"$remote\" |\n> ...\n> - done)\n> +'')\n> + case \"$reflist\" in\n> + *:refs/*)\n> ...\n>\n> Notice the first '-' and '+' lines of second hunk are identical?\n>\n> There is another interesting thing. This is running diff\n> between 52e8a6^2 and 52d8a6 blobs, but if I change them slightly\n> so that the first hunk is not different, then this anomaly\n> disappears.\n\nCould you send me the two files that creates the above diff?\n\n\n- Davide\n"},{"id":"18235","messageId":"7vzmj3k7x9.fsf@assigned-by-dhcp.cox.net","threadId":"3771","inReplyTo":"Pine.LNX.4.64.0604021035130.30097@alien.or.mcafeemobile.com","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-02T21:02:26Z","receivedAt":"2006-04-02T21:02:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Davide Libenzi writes:\n\n> On Sun, 2 Apr 2006, Junio C Hamano wrote:\n>\n>> $ git diff-tree -p 52e8a6^2 52d8a6 -- git-fetch.sh\n>>\n>> shows a change that trivially is redundant, like this:\n>>\n>> diff --git a/git-fetch.sh b/git-fetch.sh\n>> index b4325d9..de4f011 100755\n>> --- a/git-fetch.sh\n>> +++ b/git-fetch.sh\n>> @@ -320,7 +320,7 @@ fetch_main () {\n>>..\n>> Notice the first '-' and '+' lines of second hunk are identical?\n>>\n>> There is another interesting thing. This is running diff\n>> between 52e8a6^2 and 52d8a6 blobs, but if I change them slightly\n>> so that the first hunk is not different, then this anomaly\n>> disappears.\n>\n> Could you send me the two files that creates the above diff?\n\nI should have tried your pristine xdiff code myself before\nbothering you, but I haven't (sorry).\n\nThe problem is from the \"stripped down\" version we use in git,\nso you may or may not see the problem in your version. Attached\nare the files.\n\n\n\n#!/bin/sh\n#\n\nUSAGE=' ...'\n. git-sh-setup\n. git-parse-remote\n_x40='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'\n_x40=\"$_x40$_x40$_x40$_x40$_x40$_x40$_x40$_x40\"\n\nLF='\n'\nIFS=\"$LF\"\n\nno_tags=\ntags=\nappend=\nforce=\nverbose=\nupdate_head_ok=\nexec=\nupload_pack=\nwhile case \"$#\" in 0) break ;; esac\ndo\n\tcase \"$1\" in\n\t-a|--a|--ap|--app|--appe|--appen|--append)\n\t\tappend=t\n\t\t;;\n\t--upl|--uplo|--uploa|--upload|--upload-|--upload-p|\\\n\t--upload-pa|--upload-pac|--upload-pack)\n\t\tshift\n\t\texec=\"--exec=$1\" \n\t\tupload_pack=\"-u $1\"\n\t\t;;\n\t-f|--f|--fo|--for|--forc|--force)\n\t\tforce=t\n\t\t;;\n\t-t|--t|--ta|--tag|--tags)\n\t\ttags=t\n\t\t;;\n\t-n|--n|--no|--no-|--no-t|--no-ta|--no-tag|--no-tags)\n\t\tno_tags=t\n\t\t;;\n\t-u|--u|--up|--upd|--upda|--updat|--update|--update-|--update-h|\\\n\t--update-he|--update-hea|--update-head|--update-head-|\\\n\t--update-head-o|--update-head-ok)\n\t\tupdate_head_ok=t\n\t\t;;\n\t-v|--verbose)\n\t\tverbose=Yes\n\t\t;;\n\t-k|--k|--ke|--kee|--keep)\n\t\tkeep=--keep\n\t\t;;\n\t-*)\n\t\tusage\n\t\t;;\n\t*)\n\t\tbreak\n\t\t;;\n\tesac\n\tshift\ndone\n\ncase \"$#\" in\n0)\n\ttest -f \"$GIT_DIR/branches/origin\" ||\n\t\ttest -f \"$GIT_DIR/remotes/origin\" ||\n\t\t\tdie \"Where do you want to fetch from today?\"\n\tset origin ;;\nesac\n\nremote_nick=\"$1\"\nremote=$(get_remote_url \"$@\")\nrefs=\nrref=\nrsync_slurped_objects=\n\nif test \"\" = \"$append\"\nthen\n\t: >\"$GIT_DIR/FETCH_HEAD\"\nfi\n\nappend_fetch_head () {\n head_=\"$1\"\n remote_=\"$2\"\n remote_name_=\"$3\"\n remote_nick_=\"$4\"\n local_name_=\"$5\"\n case \"$6\" in\n t) not_for_merge_='not-for-merge' ;;\n '') not_for_merge_= ;;\n esac\n\n # remote-nick is the URL given on the command line (or a shorthand)\n # remote-name is the $GIT_DIR relative refs/ path we computed\n # for this refspec.\n case \"$remote_name_\" in\n HEAD)\n\tnote_= ;;\n refs/heads/*)\n\tnote_=\"$(expr \"$remote_name_\" : 'refs/heads/\\(.*\\)')\"\n\tnote_=\"branch '$note_' of \" ;;\n refs/tags/*)\n\tnote_=\"$(expr \"$remote_name_\" : 'refs/tags/\\(.*\\)')\"\n\tnote_=\"tag '$note_' of \" ;;\n *)\n\tnote_=\"$remote_name of \" ;;\n esac\n remote_1_=$(expr \"$remote_\" : '\\(.*\\)\\.git/*$') &&\n\tremote_=\"$remote_1_\"\n note_=\"$note_$remote_\"\n\n # 2.6.11-tree tag would not be happy to be fed to resolve.\n if git-cat-file commit \"$head_\" >/dev/null 2>&1\n then\n\theadc_=$(git-rev-parse --verify \"$head_^0\") || exit\n\techo \"$headc_\t$not_for_merge_\t$note_\" >>\"$GIT_DIR/FETCH_HEAD\"\n\t[ \"$verbose\" ] && echo >&2 \"* committish: $head_\"\n\t[ \"$verbose\" ] && echo >&2 \" $note_\"\n else\n\techo \"$head_\tnot-for-merge\t$note_\" >>\"$GIT_DIR/FETCH_HEAD\"\n\t[ \"$verbose\" ] && echo >&2 \"* non-commit: $head_\"\n\t[ \"$verbose\" ] && echo >&2 \" $note_\"\n fi\n if test \"$local_name_\" != \"\"\n then\n\t# We are storing the head locally. Make sure that it is\n\t# a fast forward (aka \"reverse push\").\n\tfast_forward_local \"$local_name_\" \"$head_\" \"$note_\"\n fi\n}\n\nfast_forward_local () {\n mkdir -p \"$(dirname \"$GIT_DIR/$1\")\"\n case \"$1\" in\n refs/tags/*)\n\t# Tags need not be pointing at commits so there\n\t# is no way to guarantee \"fast-forward\" anyway.\n\tif test -f \"$GIT_DIR/$1\"\n\tthen\n\t\tif now_=$(cat \"$GIT_DIR/$1\") && test \"$now_\" = \"$2\"\n\t\tthen\n\t\t\t[ \"$verbose\" ] && echo >&2 \"* $1: same as $3\"\n\t\telse\n\t\t\techo >&2 \"* $1: updating with $3\"\n\t\tfi\n\telse\n\t\techo >&2 \"* $1: storing $3\"\n\tfi\n\tgit-update-ref \"$1\" \"$2\" \n\t;;\n\n refs/heads/*)\n\t# $1 is the ref being updated.\n\t# $2 is the new value for the ref.\n\tlocal=$(git-rev-parse --verify \"$1^0\" 2>/dev/null)\n\tif test \"$local\"\n\tthen\n\t # Require fast-forward.\n\t mb=$(git-merge-base \"$local\" \"$2\") &&\n\t case \"$2,$mb\" in\n\t $local,*)\n\t\techo >&2 \"* $1: same as $3\"\n\t\t;;\n\t *,$local)\n\t\techo >&2 \"* $1: fast forward to $3\"\n\t\tgit-update-ref \"$1\" \"$2\" \"$local\"\n\t\t;;\n\t *)\n\t\tfalse\n\t\t;;\n\t esac || {\n\t\techo >&2 \"* $1: does not fast forward to $3;\"\n\t\tcase \",$force,$single_force,\" in\n\t\t*,t,*)\n\t\t\techo >&2 \" forcing update.\"\n\t\t\tgit-update-ref \"$1\" \"$2\" \"$local\"\n\t\t\t;;\n\t\t*)\n\t\t\techo >&2 \" not updating.\"\n\t\t\t;;\n\t\tesac\n\t }\n\telse\n\t echo >&2 \"* $1: storing $3\"\n\t git-update-ref \"$1\" \"$2\"\n\tfi\n\t;;\n esac\n}\n\ncase \"$update_head_ok\" in\n'')\n\torig_head=$(git-rev-parse --verify HEAD 2>/dev/null)\n\t;;\nesac\n\n# If --tags (and later --heads or --all) is specified, then we are\n# not talking about defaults stored in Pull: line of remotes or\n# branches file, and just fetch those and refspecs explicitly given.\n# Otherwise we do what we always did.\n\nreflist=$(get_remote_refs_for_fetch \"$@\")\nif test \"$tags\"\nthen\n\ttaglist=$(IFS=\"\t\" &&\n\t\t git-ls-remote $upload_pack --tags \"$remote\" |\n\t while read sha1 name\n\t\t do\n\t\t\tcase \"$name\" in\n\t\t\t(*^*) continue ;;\n\t\t\tesac\n\t\t \tif git-check-ref-format \"$name\"\n\t\t\tthen\n\t\t\t echo \".${name}:${name}\"\n\t\t\telse\n\t\t\t echo >&2 \"warning: tag ${name} ignored\"\n\t\t\tfi\n\t\t done)\n\tif test \"$#\" -gt 1\n\tthen\n\t\t# remote URL plus explicit refspecs; we need to merge them.\n\t\treflist=\"$reflist$LF$taglist\"\n\telse\n\t\t# No explicit refspecs; fetch tags only.\n\t\treflist=$taglist\n\tfi\nfi\n\nfetch_main () {\n reflist=\"$1\"\n refs=\n\n for ref in $reflist\n do\n refs=\"$refs$LF$ref\"\n\n # These are relative path from $GIT_DIR, typically starting at refs/\n # but may be HEAD\n if expr \"$ref\" : '\\.' >/dev/null\n then\n\t not_for_merge=t\n\t ref=$(expr \"$ref\" : '\\.\\(.*\\)')\n else\n\t not_for_merge=\n fi\n if expr \"$ref\" : '\\+' >/dev/null\n then\n\t single_force=t\n\t ref=$(expr \"$ref\" : '\\+\\(.*\\)')\n else\n\t single_force=\n fi\n remote_name=$(expr \"$ref\" : '\\([^:]*\\):')\n local_name=$(expr \"$ref\" : '[^:]*:\\(.*\\)')\n\n rref=\"$rref$LF$remote_name\"\n\n # There are transports that can fetch only one head at a time...\n case \"$remote\" in\n http://* | https://*)\n\t if [ -n \"$GIT_SSL_NO_VERIFY\" ]; then\n\t curl_extra_args=\"-k\"\n\t fi\n\t remote_name_quoted=$(perl -e '\n\t my $u = $ARGV[0];\n\t $u =~ s{([^-a-zA-Z0-9/.])}{sprintf\"%%%02x\",ord($1)}eg;\n\t print \"$u\";\n\t ' \"$remote_name\")\n\t head=$(curl -nsfL $curl_extra_args \"$remote/$remote_name_quoted\") &&\n\t expr \"$head\" : \"$_x40\\$\" >/dev/null ||\n\t\t die \"Failed to fetch $remote_name from $remote\"\n\t echo >&2 Fetching \"$remote_name from $remote\" using http\n\t git-http-fetch -v -a \"$head\" \"$remote/\" || exit\n\t ;;\n rsync://*)\n\t TMP_HEAD=\"$GIT_DIR/TMP_HEAD\"\n\t rsync -L -q \"$remote/$remote_name\" \"$TMP_HEAD\" || exit 1\n\t head=$(git-rev-parse --verify TMP_HEAD)\n\t rm -f \"$TMP_HEAD\"\n\t test \"$rsync_slurped_objects\" || {\n\t rsync -av --ignore-existing --exclude info \\\n\t\t \"$remote/objects/\" \"$GIT_OBJECT_DIRECTORY/\" || exit\n\n\t # Look at objects/info/alternates for rsync -- http will\n\t # support it natively and git native ones will do it on\n\t # the remote end. Not having that file is not a crime.\n\t rsync -q \"$remote/objects/info/alternates\" \\\n\t\t \"$GIT_DIR/TMP_ALT\" 2>/dev/null ||\n\t\t rm -f \"$GIT_DIR/TMP_ALT\"\n\t if test -f \"$GIT_DIR/TMP_ALT\"\n\t then\n\t\t resolve_alternates \"$remote\" <\"$GIT_DIR/TMP_ALT\" |\n\t\t while read alt\n\t\t do\n\t\t case \"$alt\" in 'bad alternate: '*) die \"$alt\";; esac\n\t\t echo >&2 \"Getting alternate: $alt\"\n\t\t rsync -av --ignore-existing --exclude info \\\n\t\t \"$alt\" \"$GIT_OBJECT_DIRECTORY/\" || exit\n\t\t done\n\t\t rm -f \"$GIT_DIR/TMP_ALT\"\n\t fi\n\t rsync_slurped_objects=t\n\t }\n\t ;;\n *)\n\t # We will do git native transport with just one call later.\n\t continue ;;\n esac\n\n append_fetch_head \"$head\" \"$remote\" \\\n\t \"$remote_name\" \"$remote_nick\" \"$local_name\" \"$not_for_merge\"\n\n done\n\n case \"$remote\" in\n http://* | https://* | rsync://* )\n ;; # we are already done.\n *)\n ( : subshell because we muck with IFS\n IFS=\" \t$LF\"\n (\n\t git-fetch-pack $exec $keep \"$remote\" $rref || echo failed \"$remote\"\n ) |\n while read sha1 remote_name\n do\n\t case \"$sha1\" in\n\t failed)\n\t\t echo >&2 \"Fetch failure: $remote\"\n\t\t exit 1 ;;\n\t esac\n\t found=\n\t single_force=\n\t for ref in $refs\n\t do\n\t case \"$ref\" in\n\t +$remote_name:*)\n\t\t single_force=t\n\t\t not_for_merge=\n\t\t found=\"$ref\"\n\t\t break ;;\n\t .+$remote_name:*)\n\t\t single_force=t\n\t\t not_for_merge=t\n\t\t found=\"$ref\"\n\t\t break ;;\n\t .$remote_name:*)\n\t\t not_for_merge=t\n\t\t found=\"$ref\"\n\t\t break ;;\n\t $remote_name:*)\n\t\t not_for_merge=\n\t\t found=\"$ref\"\n\t\t break ;;\n\t esac\n\t done\n\t local_name=$(expr \"$found\" : '[^:]*:\\(.*\\)')\n\t append_fetch_head \"$sha1\" \"$remote\" \\\n\t\t \"$remote_name\" \"$remote_nick\" \"$local_name\" \"$not_for_merge\"\n done\n ) || exit ;;\n esac\n\n}\n\nfetch_main \"$reflist\"\n\n# automated tag following\ncase \"$no_tags$tags\" in\n'')\n\ttaglist=$(IFS=\" \" &&\n\tgit-ls-remote $upload_pack --tags \"$remote\" |\n\tsed -ne 's|^\\([0-9a-f]*\\)[ \t]\\(refs/tags/.*\\)^{}$|\\1 \\2|p' |\n\twhile read sha1 name\n\tdo\n\t\ttest -f \"$GIT_DIR/$name\" && continue\n\t \tgit-check-ref-format \"$name\" || {\n\t\t\techo >&2 \"warning: tag ${name} ignored\"\n\t\t\tcontinue\n\t\t}\n\t\tgit-cat-file -t \"$sha1\" >/dev/null 2>&1 || continue\n\t\techo >&2 \"Auto-following $name\"\n\t\techo \".${name}:${name}\"\n\tdone)\n\tcase \"$taglist\" in\n\t'') ;;\n\t?*)\n\t\tfetch_main \"$taglist\" ;;\n\tesac\nesac\n\n# If the original head was empty (i.e. no \"master\" yet), or\n# if we were told not to worry, we do not have to check.\ncase \",$update_head_ok,$orig_head,\" in\n*,, | t,* )\n\t;;\n*)\n\tcurr_head=$(git-rev-parse --verify HEAD 2>/dev/null)\n\tif test \"$curr_head\" != \"$orig_head\"\n\tthen\n\t \tgit-update-ref HEAD \"$orig_head\"\n\t\tdie \"Cannot fetch into the current branch.\"\n\tfi\n\t;;\nesac\n\n\n#!/bin/sh\n#\n\nUSAGE=' ...'\n. git-sh-setup\n. git-parse-remote\n_x40='[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'\n_x40=\"$_x40$_x40$_x40$_x40$_x40$_x40$_x40$_x40\"\n\nLF='\n'\nIFS=\"$LF\"\n\nno_tags=\ntags=\nappend=\nforce=\nverbose=\nupdate_head_ok=\nexec=\nupload_pack=\nwhile case \"$#\" in 0) break ;; esac\ndo\n\tcase \"$1\" in\n\t-a|--a|--ap|--app|--appe|--appen|--append)\n\t\tappend=t\n\t\t;;\n\t--upl|--uplo|--uploa|--upload|--upload-|--upload-p|\\\n\t--upload-pa|--upload-pac|--upload-pack)\n\t\tshift\n\t\texec=\"--exec=$1\" \n\t\tupload_pack=\"-u $1\"\n\t\t;;\n\t-f|--f|--fo|--for|--forc|--force)\n\t\tforce=t\n\t\t;;\n\t-t|--t|--ta|--tag|--tags)\n\t\ttags=t\n\t\t;;\n\t-n|--n|--no|--no-|--no-t|--no-ta|--no-tag|--no-tags)\n\t\tno_tags=t\n\t\t;;\n\t-u|--u|--up|--upd|--upda|--updat|--update|--update-|--update-h|\\\n\t--update-he|--update-hea|--update-head|--update-head-|\\\n\t--update-head-o|--update-head-ok)\n\t\tupdate_head_ok=t\n\t\t;;\n\t-v|--verbose)\n\t\tverbose=Yes\n\t\t;;\n\t-k|--k|--ke|--kee|--keep)\n\t\tkeep=--keep\n\t\t;;\n\t-*)\n\t\tusage\n\t\t;;\n\t*)\n\t\tbreak\n\t\t;;\n\tesac\n\tshift\ndone\n\ncase \"$#\" in\n0)\n\ttest -f \"$GIT_DIR/branches/origin\" ||\n\t\ttest -f \"$GIT_DIR/remotes/origin\" ||\n\t\t\tdie \"Where do you want to fetch from today?\"\n\tset origin ;;\nesac\n\nremote_nick=\"$1\"\nremote=$(get_remote_url \"$@\")\nrefs=\nrref=\nrsync_slurped_objects=\n\nif test \"\" = \"$append\"\nthen\n\t: >\"$GIT_DIR/FETCH_HEAD\"\nfi\n\nappend_fetch_head () {\n head_=\"$1\"\n remote_=\"$2\"\n remote_name_=\"$3\"\n remote_nick_=\"$4\"\n local_name_=\"$5\"\n case \"$6\" in\n t) not_for_merge_='not-for-merge' ;;\n '') not_for_merge_= ;;\n esac\n\n # remote-nick is the URL given on the command line (or a shorthand)\n # remote-name is the $GIT_DIR relative refs/ path we computed\n # for this refspec.\n case \"$remote_name_\" in\n HEAD)\n\tnote_= ;;\n refs/heads/*)\n\tnote_=\"$(expr \"$remote_name_\" : 'refs/heads/\\(.*\\)')\"\n\tnote_=\"branch '$note_' of \" ;;\n refs/tags/*)\n\tnote_=\"$(expr \"$remote_name_\" : 'refs/tags/\\(.*\\)')\"\n\tnote_=\"tag '$note_' of \" ;;\n *)\n\tnote_=\"$remote_name of \" ;;\n esac\n remote_1_=$(expr \"$remote_\" : '\\(.*\\)\\.git/*$') &&\n\tremote_=\"$remote_1_\"\n note_=\"$note_$remote_\"\n\n # 2.6.11-tree tag would not be happy to be fed to resolve.\n if git-cat-file commit \"$head_\" >/dev/null 2>&1\n then\n\theadc_=$(git-rev-parse --verify \"$head_^0\") || exit\n\techo \"$headc_\t$not_for_merge_\t$note_\" >>\"$GIT_DIR/FETCH_HEAD\"\n\t[ \"$verbose\" ] && echo >&2 \"* committish: $head_\"\n\t[ \"$verbose\" ] && echo >&2 \" $note_\"\n else\n\techo \"$head_\tnot-for-merge\t$note_\" >>\"$GIT_DIR/FETCH_HEAD\"\n\t[ \"$verbose\" ] && echo >&2 \"* non-commit: $head_\"\n\t[ \"$verbose\" ] && echo >&2 \" $note_\"\n fi\n if test \"$local_name_\" != \"\"\n then\n\t# We are storing the head locally. Make sure that it is\n\t# a fast forward (aka \"reverse push\").\n\tfast_forward_local \"$local_name_\" \"$head_\" \"$note_\"\n fi\n}\n\nfast_forward_local () {\n mkdir -p \"$(dirname \"$GIT_DIR/$1\")\"\n case \"$1\" in\n refs/tags/*)\n\t# Tags need not be pointing at commits so there\n\t# is no way to guarantee \"fast-forward\" anyway.\n\tif test -f \"$GIT_DIR/$1\"\n\tthen\n\t\tif now_=$(cat \"$GIT_DIR/$1\") && test \"$now_\" = \"$2\"\n\t\tthen\n\t\t\t[ \"$verbose\" ] && echo >&2 \"* $1: same as $3\"\n\t\telse\n\t\t\techo >&2 \"* $1: updating with $3\"\n\t\tfi\n\telse\n\t\techo >&2 \"* $1: storing $3\"\n\tfi\n\tgit-update-ref \"$1\" \"$2\" \n\t;;\n\n refs/heads/*)\n\t# $1 is the ref being updated.\n\t# $2 is the new value for the ref.\n\tlocal=$(git-rev-parse --verify \"$1^0\" 2>/dev/null)\n\tif test \"$local\"\n\tthen\n\t # Require fast-forward.\n\t mb=$(git-merge-base \"$local\" \"$2\") &&\n\t case \"$2,$mb\" in\n\t $local,*)\n\t\techo >&2 \"* $1: same as $3\"\n\t\t;;\n\t *,$local)\n\t\techo >&2 \"* $1: fast forward to $3\"\n\t\tgit-update-ref \"$1\" \"$2\" \"$local\"\n\t\t;;\n\t *)\n\t\tfalse\n\t\t;;\n\t esac || {\n\t\techo >&2 \"* $1: does not fast forward to $3;\"\n\t\tcase \",$force,$single_force,\" in\n\t\t*,t,*)\n\t\t\techo >&2 \" forcing update.\"\n\t\t\tgit-update-ref \"$1\" \"$2\" \"$local\"\n\t\t\t;;\n\t\t*)\n\t\t\techo >&2 \" not updating.\"\n\t\t\t;;\n\t\tesac\n\t }\n\telse\n\t echo >&2 \"* $1: storing $3\"\n\t git-update-ref \"$1\" \"$2\"\n\tfi\n\t;;\n esac\n}\n\ncase \"$update_head_ok\" in\n'')\n\torig_head=$(git-rev-parse --verify HEAD 2>/dev/null)\n\t;;\nesac\n\n# If --tags (and later --heads or --all) is specified, then we are\n# not talking about defaults stored in Pull: line of remotes or\n# branches file, and just fetch those and refspecs explicitly given.\n# Otherwise we do what we always did.\n\nreflist=$(get_remote_refs_for_fetch \"$@\")\nif test \"$tags\"\nthen\n\ttaglist=$(IFS=\"\t\" &&\n\t\t git-ls-remote $upload_pack --tags \"$remote\" |\n\t while read sha1 name\n\t\t do\n\t\t\tcase \"$name\" in\n\t\t\t(*^*) continue ;;\n\t\t\tesac\n\t\t \tif git-check-ref-format \"$name\"\n\t\t\tthen\n\t\t\t echo \".${name}:${name}\"\n\t\t\telse\n\t\t\t echo >&2 \"warning: tag ${name} ignored\"\n\t\t\tfi\n\t\t done)\n\tif test \"$#\" -gt 1\n\tthen\n\t\t# remote URL plus explicit refspecs; we need to merge them.\n\t\treflist=\"$reflist$LF$taglist\"\n\telse\n\t\t# No explicit refspecs; fetch tags only.\n\t\treflist=$taglist\n\tfi\nfi\n\nfetch_main () {\n reflist=\"$1\"\n refs=\n\n for ref in $reflist\n do\n refs=\"$refs$LF$ref\"\n\n # These are relative path from $GIT_DIR, typically starting at refs/\n # but may be HEAD\n if expr \"$ref\" : '\\.' >/dev/null\n then\n\t not_for_merge=t\n\t ref=$(expr \"$ref\" : '\\.\\(.*\\)')\n else\n\t not_for_merge=\n fi\n if expr \"$ref\" : '\\+' >/dev/null\n then\n\t single_force=t\n\t ref=$(expr \"$ref\" : '\\+\\(.*\\)')\n else\n\t single_force=\n fi\n remote_name=$(expr \"$ref\" : '\\([^:]*\\):')\n local_name=$(expr \"$ref\" : '[^:]*:\\(.*\\)')\n\n rref=\"$rref$LF$remote_name\"\n\n # There are transports that can fetch only one head at a time...\n case \"$remote\" in\n http://* | https://*)\n\t if [ -n \"$GIT_SSL_NO_VERIFY\" ]; then\n\t curl_extra_args=\"-k\"\n\t fi\n\t remote_name_quoted=$(perl -e '\n\t my $u = $ARGV[0];\n\t $u =~ s{([^-a-zA-Z0-9/.])}{sprintf\"%%%02x\",ord($1)}eg;\n\t print \"$u\";\n\t ' \"$remote_name\")\n\t head=$(curl -nsfL $curl_extra_args \"$remote/$remote_name_quoted\") &&\n\t expr \"$head\" : \"$_x40\\$\" >/dev/null ||\n\t\t die \"Failed to fetch $remote_name from $remote\"\n\t echo >&2 Fetching \"$remote_name from $remote\" using http\n\t git-http-fetch -v -a \"$head\" \"$remote/\" || exit\n\t ;;\n rsync://*)\n\t TMP_HEAD=\"$GIT_DIR/TMP_HEAD\"\n\t rsync -L -q \"$remote/$remote_name\" \"$TMP_HEAD\" || exit 1\n\t head=$(git-rev-parse --verify TMP_HEAD)\n\t rm -f \"$TMP_HEAD\"\n\t test \"$rsync_slurped_objects\" || {\n\t rsync -av --ignore-existing --exclude info \\\n\t\t \"$remote/objects/\" \"$GIT_OBJECT_DIRECTORY/\" || exit\n\n\t # Look at objects/info/alternates for rsync -- http will\n\t # support it natively and git native ones will do it on\n\t # the remote end. Not having that file is not a crime.\n\t rsync -q \"$remote/objects/info/alternates\" \\\n\t\t \"$GIT_DIR/TMP_ALT\" 2>/dev/null ||\n\t\t rm -f \"$GIT_DIR/TMP_ALT\"\n\t if test -f \"$GIT_DIR/TMP_ALT\"\n\t then\n\t\t resolve_alternates \"$remote\" <\"$GIT_DIR/TMP_ALT\" |\n\t\t while read alt\n\t\t do\n\t\t case \"$alt\" in 'bad alternate: '*) die \"$alt\";; esac\n\t\t echo >&2 \"Getting alternate: $alt\"\n\t\t rsync -av --ignore-existing --exclude info \\\n\t\t \"$alt\" \"$GIT_OBJECT_DIRECTORY/\" || exit\n\t\t done\n\t\t rm -f \"$GIT_DIR/TMP_ALT\"\n\t fi\n\t rsync_slurped_objects=t\n\t }\n\t ;;\n *)\n\t # We will do git native transport with just one call later.\n\t continue ;;\n esac\n\n append_fetch_head \"$head\" \"$remote\" \\\n\t \"$remote_name\" \"$remote_nick\" \"$local_name\" \"$not_for_merge\"\n\n done\n\n case \"$remote\" in\n http://* | https://* | rsync://* )\n ;; # we are already done.\n *)\n ( : subshell because we muck with IFS\n IFS=\" \t$LF\"\n (\n\t git-fetch-pack $exec $keep --thin \"$remote\" $rref || echo failed \"$remote\"\n ) |\n while read sha1 remote_name\n do\n\t case \"$sha1\" in\n\t failed)\n\t\t echo >&2 \"Fetch failure: $remote\"\n\t\t exit 1 ;;\n\t esac\n\t found=\n\t single_force=\n\t for ref in $refs\n\t do\n\t case \"$ref\" in\n\t +$remote_name:*)\n\t\t single_force=t\n\t\t not_for_merge=\n\t\t found=\"$ref\"\n\t\t break ;;\n\t .+$remote_name:*)\n\t\t single_force=t\n\t\t not_for_merge=t\n\t\t found=\"$ref\"\n\t\t break ;;\n\t .$remote_name:*)\n\t\t not_for_merge=t\n\t\t found=\"$ref\"\n\t\t break ;;\n\t $remote_name:*)\n\t\t not_for_merge=\n\t\t found=\"$ref\"\n\t\t break ;;\n\t esac\n\t done\n\t local_name=$(expr \"$found\" : '[^:]*:\\(.*\\)')\n\t append_fetch_head \"$sha1\" \"$remote\" \\\n\t\t \"$remote_name\" \"$remote_nick\" \"$local_name\" \"$not_for_merge\"\n done\n ) || exit ;;\n esac\n\n}\n\nfetch_main \"$reflist\"\n\n# automated tag following\ncase \"$no_tags$tags\" in\n'')\n\tcase \"$reflist\" in\n\t*:refs/*)\n\t\t# effective only when we are following remote branch\n\t\t# using local tracking branch.\n\t\ttaglist=$(IFS=\" \" &&\n\t\tgit-ls-remote $upload_pack --tags \"$remote\" |\n\t\tsed -ne 's|^\\([0-9a-f]*\\)[ \t]\\(refs/tags/.*\\)^{}$|\\1 \\2|p' |\n\t\twhile read sha1 name\n\t\tdo\n\t\t\ttest -f \"$GIT_DIR/$name\" && continue\n\t\t\tgit-check-ref-format \"$name\" || {\n\t\t\t\techo >&2 \"warning: tag ${name} ignored\"\n\t\t\t\tcontinue\n\t\t\t}\n\t\t\tgit-cat-file -t \"$sha1\" >/dev/null 2>&1 || continue\n\t\t\techo >&2 \"Auto-following $name\"\n\t\t\techo \".${name}:${name}\"\n\t\tdone)\n\tesac\n\tcase \"$taglist\" in\n\t'') ;;\n\t?*)\n\t\tfetch_main \"$taglist\" ;;\n\tesac\nesac\n\n# If the original head was empty (i.e. no \"master\" yet), or\n# if we were told not to worry, we do not have to check.\ncase \",$update_head_ok,$orig_head,\" in\n*,, | t,* )\n\t;;\n*)\n\tcurr_head=$(git-rev-parse --verify HEAD 2>/dev/null)\n\tif test \"$curr_head\" != \"$orig_head\"\n\tthen\n\t \tgit-update-ref HEAD \"$orig_head\"\n\t\tdie \"Cannot fetch into the current branch.\"\n\tfi\n\t;;\nesac\n"},{"id":"18237","messageId":"Pine.LNX.4.64.0604021411300.23419@g5.osdl.org","threadId":"3771","inReplyTo":"7vzmj3k7x9.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-04-02T21:16:24Z","receivedAt":"2006-04-02T21:16:24Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 2 Apr 2006, Junio C Hamano wrote:\n> \n> I should have tried your pristine xdiff code myself before\n> bothering you, but I haven't (sorry).\n\nIt definitely happens with plain libxdiff-0.17 too.\n\nIn general, unless it's related to the \"\\ No newline\" or the extra stuff \non the \"@@\"-line, I'd be very surprised if we have any differences in the \ndiff output wrt libxdiff-0.17. I was really pretty careful, and didn't \nchange the code at all, just removed unnecessary files and functions.\n\n\t\tLinus\n"},{"id":"18242","messageId":"Pine.LNX.4.64.0604021454560.30205@alien.or.mcafeemobile.com","threadId":"3771","inReplyTo":"7vzmj3k7x9.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-04-02T22:14:16Z","receivedAt":"2006-04-02T22:14:16Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Sun, 2 Apr 2006, Junio C Hamano wrote:\n\n> I should have tried your pristine xdiff code myself before\n> bothering you, but I haven't (sorry).\n>\n> The problem is from the \"stripped down\" version we use in git,\n> so you may or may not see the problem in your version. Attached\n> are the files.\n\nYes, it does even vanilla libxdiff ;) It's not a problem though, since it \nis created in xdl_cleanup_records() that tries to do a fast pass over the \nrecords to try to simplify the real diff operation. In trying to be fast, \nonly hashes are compared, and it happens that the hash for \"'')\" collides \nwith another one (try to replace one of the \"'')\" chars with another one). \nWhy is this not a problem? Because what this lead to is only lines to be \nmarked as changed, with a probability of about N/2^(8 * sizeof(long) - 1), \neven though they are not. And this happens only during sequential groups \nof lines changed, that is when the hash-colliding line is either at the \nbegin or the end of the run.\n\n\n\n- Davide\n"},{"id":"18243","messageId":"Pine.LNX.4.64.0604021517350.30205@alien.or.mcafeemobile.com","threadId":"3771","inReplyTo":"Pine.LNX.4.64.0604021411300.23419@g5.osdl.org","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-04-02T22:18:55Z","receivedAt":"2006-04-02T22:18:55Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Sun, 2 Apr 2006, Linus Torvalds wrote:\n\n> On Sun, 2 Apr 2006, Junio C Hamano wrote:\n>>\n>> I should have tried your pristine xdiff code myself before\n>> bothering you, but I haven't (sorry).\n>\n> It definitely happens with plain libxdiff-0.17 too.\n>\n> In general, unless it's related to the \"\\ No newline\" or the extra stuff\n> on the \"@@\"-line, I'd be very surprised if we have any differences in the\n> diff output wrt libxdiff-0.17. I was really pretty careful, and didn't\n> change the code at all, just removed unnecessary files and functions.\n\nSo it does 0.18, that contains the \"\\ No newline\" handling for text diff \nand patch. See my reply to Junio also.\n\n\n\n- Davide\n"},{"id":"18250","messageId":"Pine.LNX.4.64.0604021749580.23419@g5.osdl.org","threadId":"3771","inReplyTo":"Pine.LNX.4.64.0604021454560.30205@alien.or.mcafeemobile.com","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-04-03T00:52:02Z","receivedAt":"2006-04-03T00:52:02Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 2 Apr 2006, Davide Libenzi wrote:\n> \n> Yes, it does even vanilla libxdiff ;) It's not a problem though, since it is\n> created in xdl_cleanup_records() that tries to do a fast pass over the records\n> to try to simplify the real diff operation. In trying to be fast, only hashes\n> are compared, and it happens that the hash for \"'')\" collides with another one\n> (try to replace one of the \"'')\" chars with another one). Why is this not a\n> problem? Because what this lead to is only lines to be marked as changed, with\n> a probability of about N/2^(8 * sizeof(long) - 1), even though they are not.\n> And this happens only during sequential groups of lines changed, that is when\n> the hash-colliding line is either at the begin or the end of the run.\n\nHmm. It's still ugly, though. No possibility to have a \"clean up identical \ninitial and final lines\" stage to get rid of extraneous bogus diffs?\n\nI look at diffs a lot, and while this may be rare, if I were to end up \nhaving to wonder what the difference is and it turns out that it's just \ndue to a libxdelta thing, I'd be a bit irritated and wish it gave me a \nproper diff..\n\n\t\tLinus\n"},{"id":"18255","messageId":"Pine.LNX.4.64.0604022022390.10401@alien.or.mcafeemobile.com","threadId":"3771","inReplyTo":"Pine.LNX.4.64.0604021749580.23419@g5.osdl.org","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-04-03T03:26:52Z","receivedAt":"2006-04-03T03:26:52Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Sun, 2 Apr 2006, Linus Torvalds wrote:\n\n>\n>\n> On Sun, 2 Apr 2006, Davide Libenzi wrote:\n>>\n>> Yes, it does even vanilla libxdiff ;) It's not a problem though, since it is\n>> created in xdl_cleanup_records() that tries to do a fast pass over the records\n>> to try to simplify the real diff operation. In trying to be fast, only hashes\n>> are compared, and it happens that the hash for \"'')\" collides with another one\n>> (try to replace one of the \"'')\" chars with another one). Why is this not a\n>> problem? Because what this lead to is only lines to be marked as changed, with\n>> a probability of about N/2^(8 * sizeof(long) - 1), even though they are not.\n>> And this happens only during sequential groups of lines changed, that is when\n>> the hash-colliding line is either at the begin or the end of the run.\n>\n> Hmm. It's still ugly, though. No possibility to have a \"clean up identical\n> initial and final lines\" stage to get rid of extraneous bogus diffs?\n\nIt does ;) If you make the second hunk (the one with the '') line) to be \nthe first, the shrink-initial-and-final lines optimizations will make it \neat the '') line.\n\n\n> I look at diffs a lot, and while this may be rare, if I were to end up\n> having to wonder what the difference is and it turns out that it's just\n> due to a libxdelta thing, I'd be a bit irritated and wish it gave me a\n> proper diff..\n\nTomorrow I'll take a look at it.\n\n\n- Davide\n"},{"id":"18259","messageId":"Pine.LNX.4.64.0604022116060.3781@g5.osdl.org","threadId":"3771","inReplyTo":"Pine.LNX.4.64.0604022022390.10401@alien.or.mcafeemobile.com","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-04-03T04:19:58Z","receivedAt":"2006-04-03T04:19:58Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 2 Apr 2006, Davide Libenzi wrote:\n> \n> Tomorrow I'll take a look at it.\n\nThanks. I've made the first \"release\" (2.6.17-rc1) with the new built-in \ndiff, let's see if somebody has any issues.\n\nBut just the fact that I could do an almost 24MB diff (6MB compressed) \nwith 738 _thousand_ lines in about 4 seconds is damn nice. The script I \nuse to cut releases (logs, diffstats, tar-files etc) used to take a long \ntime with BK, these days it's a couple of seconds.\n\n\t\tLinus\n"},{"id":"18264","messageId":"Pine.LNX.4.64.0604022124440.10401@alien.or.mcafeemobile.com","threadId":"3771","inReplyTo":"Pine.LNX.4.64.0604022116060.3781@g5.osdl.org","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-04-03T04:30:03Z","receivedAt":"2006-04-03T04:30:03Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Sun, 2 Apr 2006, Linus Torvalds wrote:\n\n> On Sun, 2 Apr 2006, Davide Libenzi wrote:\n>>\n>> Tomorrow I'll take a look at it.\n>\n> Thanks. I've made the first \"release\" (2.6.17-rc1) with the new built-in\n> diff, let's see if somebody has any issues.\n\nNo problem. That's only an eye-issue though, since the diff is still a \nvalid diff according to its definition where D=A-B => B+D==A && A-D==B\nFrom the day I released 0.18, xregression is continuosly running w/out any \nissue. I'll check it out though ...\n\n\n\n- Davide\n"},{"id":"18268","messageId":"7v4q1bglkp.fsf@assigned-by-dhcp.cox.net","threadId":"3771","inReplyTo":"Pine.LNX.4.64.0604022124440.10401@alien.or.mcafeemobile.com","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-03T07:33:26Z","receivedAt":"2006-04-03T07:33:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Davide Libenzi writes:\n\n> No problem. That's only an eye-issue though, since the diff is still a\n> valid diff according to its definition where D=A-B => B+D==A && A-D==B\n> From the day I released 0.18, xregression is continuosly running w/out\n> any issue. I'll check it out though ...\n\nThere is another to report, when ctxlen == 0.\n\nBetween the attached files \"diff -u0 8f352aa dd40a03\", the \nheader for a hunk with only inserted lines misidentify the\noriginal location.\n\nFor example, the first hunk says:\n\n\t@@ -0,0 +6 @@\n +#include \"diff.h\"\n\nWhich is inconsistent with what GNU diff says:\n\n\t@@ -5,0 +6 @@\n +#include \"diff.h\"\n\nI've tried this patch but it is not right; the diff between the\nattached two files show a 47-line hunk that inserts at line 400,\nthen the next 6-line hunk inserts at line 401 which is obviously\nbogus.\n\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex afaada1..3e7f999 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -244,7 +244,7 @@ int xdl_emit_hunk_hdr(long s1, long c1, \n \tmemcpy(buf, \"@@ -\", 4);\n \tnb += 4;\n \n-\tnb += xdl_num_out(buf + nb, c1 ? s1: 0);\n+\tnb += xdl_num_out(buf + nb, c1 ? s1 : (s1-1));\n \n \tif (c1 != 1) {\n \t\tmemcpy(buf + nb, \",\", 1);\n\n\n\n#include \"cache.h\"\n#include \"object.h\"\n#include \"delta.h\"\n#include \"pack.h\"\n#include \"csum-file.h\"\n#include \n#include \n\nstatic const char pack_usage[] = \"git-pack-objects [-q] [--no-reuse-delta] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} < object-list\";\n\nstruct object_entry {\n\tunsigned char sha1[20];\n\tunsigned long size;\t/* uncompressed size */\n\tunsigned long offset;\t/* offset into the final pack file;\n\t\t\t\t * nonzero if already written.\n\t\t\t\t */\n\tunsigned int depth;\t/* delta depth */\n\tunsigned int delta_limit;\t/* base adjustment for in-pack delta */\n\tunsigned int hash;\t/* name hint hash */\n\tenum object_type type;\n\tenum object_type in_pack_type;\t/* could be delta */\n\tunsigned long delta_size;\t/* delta data size (uncompressed) */\n\tstruct object_entry *delta;\t/* delta base object */\n\tstruct packed_git *in_pack; \t/* already in pack */\n\tunsigned int in_pack_offset;\n\tstruct object_entry *delta_child; /* delitified objects who bases me */\n\tstruct object_entry *delta_sibling; /* other deltified objects who\n\t\t\t\t\t * uses the same base as me\n\t\t\t\t\t */\n};\n\n/*\n * Objects we are going to pack are colected in objects array (dynamically\n * expanded). nr_objects & nr_alloc controls this array. They are stored\n * in the order we see -- typically rev-list --objects order that gives us\n * nice \"minimum seek\" order.\n *\n * sorted-by-sha ans sorted-by-type are arrays of pointers that point at\n * elements in the objects array. The former is used to build the pack\n * index (lists object names in the ascending order to help offset lookup),\n * and the latter is used to group similar things together by try_delta()\n * heuristics.\n */\n\nstatic unsigned char object_list_sha1[20];\nstatic int non_empty = 0;\nstatic int no_reuse_delta = 0;\nstatic int local = 0;\nstatic int incremental = 0;\nstatic struct object_entry **sorted_by_sha, **sorted_by_type;\nstatic struct object_entry *objects = NULL;\nstatic int nr_objects = 0, nr_alloc = 0;\nstatic const char *base_name;\nstatic unsigned char pack_file_sha1[20];\nstatic int progress = 1;\nstatic volatile int progress_update = 0;\n\n/*\n * The object names in objects array are hashed with this hashtable,\n * to help looking up the entry by object name. Binary search from\n * sorted_by_sha is also possible but this was easier to code and faster.\n * This hashtable is built after all the objects are seen.\n */\nstatic int *object_ix = NULL;\nstatic int object_ix_hashsz = 0;\n\n/*\n * Pack index for existing packs give us easy access to the offsets into\n * corresponding pack file where each object's data starts, but the entries\n * do not store the size of the compressed representation (uncompressed\n * size is easily available by examining the pack entry header). We build\n * a hashtable of existing packs (pack_revindex), and keep reverse index\n * here -- pack index file is sorted by object name mapping to offset; this\n * pack_revindex[].revindex array is an ordered list of offsets, so if you\n * know the offset of an object, next offset is where its packed\n * representation ends.\n */\nstruct pack_revindex {\n\tstruct packed_git *p;\n\tunsigned long *revindex;\n} *pack_revindex = NULL;\nstatic int pack_revindex_hashsz = 0;\n\n/*\n * stats\n */\nstatic int written = 0;\nstatic int written_delta = 0;\nstatic int reused = 0;\nstatic int reused_delta = 0;\n\nstatic int pack_revindex_ix(struct packed_git *p)\n{\n\tunsigned int ui = (unsigned int) p;\n\tint i;\n\n\tui = ui ^ (ui >> 16); /* defeat structure alignment */\n\ti = (int)(ui % pack_revindex_hashsz);\n\twhile (pack_revindex[i].p) {\n\t\tif (pack_revindex[i].p == p)\n\t\t\treturn i;\n\t\tif (++i == pack_revindex_hashsz)\n\t\t\ti = 0;\n\t}\n\treturn -1 - i;\n}\n\nstatic void prepare_pack_ix(void)\n{\n\tint num;\n\tstruct packed_git *p;\n\tfor (num = 0, p = packed_git; p; p = p->next)\n\t\tnum++;\n\tif (!num)\n\t\treturn;\n\tpack_revindex_hashsz = num * 11;\n\tpack_revindex = xcalloc(sizeof(*pack_revindex), pack_revindex_hashsz);\n\tfor (p = packed_git; p; p = p->next) {\n\t\tnum = pack_revindex_ix(p);\n\t\tnum = - 1 - num;\n\t\tpack_revindex[num].p = p;\n\t}\n\t/* revindex elements are lazily initialized */\n}\n\nstatic int cmp_offset(const void *a_, const void *b_)\n{\n\tunsigned long a = *(unsigned long *) a_;\n\tunsigned long b = *(unsigned long *) b_;\n\tif (a < b)\n\t\treturn -1;\n\telse if (a == b)\n\t\treturn 0;\n\telse\n\t\treturn 1;\n}\n\n/*\n * Ordered list of offsets of objects in the pack.\n */\nstatic void prepare_pack_revindex(struct pack_revindex *rix)\n{\n\tstruct packed_git *p = rix->p;\n\tint num_ent = num_packed_objects(p);\n\tint i;\n\tvoid *index = p->index_base + 256;\n\n\trix->revindex = xmalloc(sizeof(unsigned long) * (num_ent + 1));\n\tfor (i = 0; i < num_ent; i++) {\n\t\tlong hl = *((long *)(index + 24 * i));\n\t\trix->revindex[i] = ntohl(hl);\n\t}\n\t/* This knows the pack format -- the 20-byte trailer\n\t * follows immediately after the last object data.\n\t */\n\trix->revindex[num_ent] = p->pack_size - 20;\n\tqsort(rix->revindex, num_ent, sizeof(unsigned long), cmp_offset);\n}\n\nstatic unsigned long find_packed_object_size(struct packed_git *p,\n\t\t\t\t\t unsigned long ofs)\n{\n\tint num;\n\tint lo, hi;\n\tstruct pack_revindex *rix;\n\tunsigned long *revindex;\n\tnum = pack_revindex_ix(p);\n\tif (num < 0)\n\t\tdie(\"internal error: pack revindex uninitialized\");\n\trix = &pack_revindex[num];\n\tif (!rix->revindex)\n\t\tprepare_pack_revindex(rix);\n\trevindex = rix->revindex;\n\tlo = 0;\n\thi = num_packed_objects(p) + 1;\n\tdo {\n\t\tint mi = (lo + hi) / 2;\n\t\tif (revindex[mi] == ofs) {\n\t\t\treturn revindex[mi+1] - ofs;\n\t\t}\n\t\telse if (ofs < revindex[mi])\n\t\t\thi = mi;\n\t\telse\n\t\t\tlo = mi + 1;\n\t} while (lo < hi);\n\tdie(\"internal error: pack revindex corrupt\");\n}\n\nstatic void *delta_against(void *buf, unsigned long size, struct object_entry *entry)\n{\n\tunsigned long othersize, delta_size;\n\tchar type[10];\n\tvoid *otherbuf = read_sha1_file(entry->delta->sha1, type, &othersize);\n\tvoid *delta_buf;\n\n\tif (!otherbuf)\n\t\tdie(\"unable to read %s\", sha1_to_hex(entry->delta->sha1));\n delta_buf = diff_delta(otherbuf, othersize,\n\t\t\t buf, size, &delta_size, 0);\n if (!delta_buf || delta_size != entry->delta_size)\n \tdie(\"delta size changed\");\n free(buf);\n free(otherbuf);\n\treturn delta_buf;\n}\n\n/*\n * The per-object header is a pretty dense thing, which is\n * - first byte: low four bits are \"size\", then three bits of \"type\",\n * and the high bit is \"size continues\".\n * - each byte afterwards: low seven bits are size continuation,\n * with the high bit being \"size continues\"\n */\nstatic int encode_header(enum object_type type, unsigned long size, unsigned char *hdr)\n{\n\tint n = 1;\n\tunsigned char c;\n\n\tif (type < OBJ_COMMIT || type > OBJ_DELTA)\n\t\tdie(\"bad type %d\", type);\n\n\tc = (type << 4) | (size & 15);\n\tsize >>= 4;\n\twhile (size) {\n\t\t*hdr++ = c | 0x80;\n\t\tc = size & 0x7f;\n\t\tsize >>= 7;\n\t\tn++;\n\t}\n\t*hdr = c;\n\treturn n;\n}\n\nstatic unsigned long write_object(struct sha1file *f, struct object_entry *entry)\n{\n\tunsigned long size;\n\tchar type[10];\n\tvoid *buf;\n\tunsigned char header[10];\n\tunsigned hdrlen, datalen;\n\tenum object_type obj_type;\n\tint to_reuse = 0;\n\n\tobj_type = entry->type;\n\tif (! entry->in_pack)\n\t\tto_reuse = 0;\t/* can't reuse what we don't have */\n\telse if (obj_type == OBJ_DELTA)\n\t\tto_reuse = 1;\t/* check_object() decided it for us */\n\telse if (obj_type != entry->in_pack_type)\n\t\tto_reuse = 0;\t/* pack has delta which is unusable */\n\telse if (entry->delta)\n\t\tto_reuse = 0;\t/* we want to pack afresh */\n\telse\n\t\tto_reuse = 1;\t/* we have it in-pack undeltified,\n\t\t\t\t * and we do not need to deltify it.\n\t\t\t\t */\n\n\tif (! to_reuse) {\n\t\tbuf = read_sha1_file(entry->sha1, type, &size);\n\t\tif (!buf)\n\t\t\tdie(\"unable to read %s\", sha1_to_hex(entry->sha1));\n\t\tif (size != entry->size)\n\t\t\tdie(\"object %s size inconsistency (%lu vs %lu)\",\n\t\t\t sha1_to_hex(entry->sha1), size, entry->size);\n\t\tif (entry->delta) {\n\t\t\tbuf = delta_against(buf, size, entry);\n\t\t\tsize = entry->delta_size;\n\t\t\tobj_type = OBJ_DELTA;\n\t\t}\n\t\t/*\n\t\t * The object header is a byte of 'type' followed by zero or\n\t\t * more bytes of length. For deltas, the 20 bytes of delta\n\t\t * sha1 follows that.\n\t\t */\n\t\thdrlen = encode_header(obj_type, size, header);\n\t\tsha1write(f, header, hdrlen);\n\n\t\tif (entry->delta) {\n\t\t\tsha1write(f, entry->delta, 20);\n\t\t\thdrlen += 20;\n\t\t}\n\t\tdatalen = sha1write_compressed(f, buf, size);\n\t\tfree(buf);\n\t}\n\telse {\n\t\tstruct packed_git *p = entry->in_pack;\n\t\tuse_packed_git(p);\n\n\t\tdatalen = find_packed_object_size(p, entry->in_pack_offset);\n\t\tbuf = p->pack_base + entry->in_pack_offset;\n\t\tsha1write(f, buf, datalen);\n\t\tunuse_packed_git(p);\n\t\thdrlen = 0; /* not really */\n\t\tif (obj_type == OBJ_DELTA)\n\t\t\treused_delta++;\n\t\treused++;\n\t}\n\tif (obj_type == OBJ_DELTA)\n\t\twritten_delta++;\n\twritten++;\n\treturn hdrlen + datalen;\n}\n\nstatic unsigned long write_one(struct sha1file *f,\n\t\t\t struct object_entry *e,\n\t\t\t unsigned long offset)\n{\n\tif (e->offset)\n\t\t/* offset starts from header size and cannot be zero\n\t\t * if it is written already.\n\t\t */\n\t\treturn offset;\n\te->offset = offset;\n\toffset += write_object(f, e);\n\t/* if we are deltified, write out its base object. */\n\tif (e->delta)\n\t\toffset = write_one(f, e->delta, offset);\n\treturn offset;\n}\n\nstatic void write_pack_file(void)\n{\n\tint i;\n\tstruct sha1file *f;\n\tunsigned long offset;\n\tstruct pack_header hdr;\n\tunsigned last_percent = 999;\n\tint do_progress = 0;\n\n\tif (!base_name)\n\t\tf = sha1fd(1, \"\");\n\telse {\n\t\tf = sha1create(\"%s-%s.%s\", base_name,\n\t\t\t sha1_to_hex(object_list_sha1), \"pack\");\n\t\tdo_progress = progress;\n\t}\n\tif (do_progress)\n\t\tfprintf(stderr, \"Writing %d objects.\\n\", nr_objects);\n\n\thdr.hdr_signature = htonl(PACK_SIGNATURE);\n\thdr.hdr_version = htonl(PACK_VERSION);\n\thdr.hdr_entries = htonl(nr_objects);\n\tsha1write(f, &hdr, sizeof(hdr));\n\toffset = sizeof(hdr);\n\tfor (i = 0; i < nr_objects; i++) {\n\t\toffset = write_one(f, objects + i, offset);\n\t\tif (do_progress) {\n\t\t\tunsigned percent = written * 100 / nr_objects;\n\t\t\tif (progress_update || percent != last_percent) {\n\t\t\t\tfprintf(stderr, \"%4u%% (%u/%u) done\\r\",\n\t\t\t\t\tpercent, written, nr_objects);\n\t\t\t\tprogress_update = 0;\n\t\t\t\tlast_percent = percent;\n\t\t\t}\n\t\t}\n\t}\n\tif (do_progress)\n\t\tfputc('\\n', stderr);\n\n\tsha1close(f, pack_file_sha1, 1);\n}\n\nstatic void write_index_file(void)\n{\n\tint i;\n\tstruct sha1file *f = sha1create(\"%s-%s.%s\", base_name, sha1_to_hex(object_list_sha1), \"idx\");\n\tstruct object_entry **list = sorted_by_sha;\n\tstruct object_entry **last = list + nr_objects;\n\tunsigned int array[256];\n\n\t/*\n\t * Write the first-level table (the list is sorted,\n\t * but we use a 256-entry lookup to be able to avoid\n\t * having to do eight extra binary search iterations).\n\t */\n\tfor (i = 0; i < 256; i++) {\n\t\tstruct object_entry **next = list;\n\t\twhile (next < last) {\n\t\t\tstruct object_entry *entry = *next;\n\t\t\tif (entry->sha1[0] != i)\n\t\t\t\tbreak;\n\t\t\tnext++;\n\t\t}\n\t\tarray[i] = htonl(next - sorted_by_sha);\n\t\tlist = next;\n\t}\n\tsha1write(f, array, 256 * sizeof(int));\n\n\t/*\n\t * Write the actual SHA1 entries..\n\t */\n\tlist = sorted_by_sha;\n\tfor (i = 0; i < nr_objects; i++) {\n\t\tstruct object_entry *entry = *list++;\n\t\tunsigned int offset = htonl(entry->offset);\n\t\tsha1write(f, &offset, 4);\n\t\tsha1write(f, entry->sha1, 20);\n\t}\n\tsha1write(f, pack_file_sha1, 20);\n\tsha1close(f, NULL, 1);\n}\n\nstatic int add_object_entry(unsigned char *sha1, unsigned int hash)\n{\n\tunsigned int idx = nr_objects;\n\tstruct object_entry *entry;\n\tstruct packed_git *p;\n\tunsigned int found_offset = 0;\n\tstruct packed_git *found_pack = NULL;\n\n\tfor (p = packed_git; p; p = p->next) {\n\t\tstruct pack_entry e;\n\t\tif (find_pack_entry_one(sha1, &e, p)) {\n\t\t\tif (incremental)\n\t\t\t\treturn 0;\n\t\t\tif (local && !p->pack_local)\n\t\t\t\treturn 0;\n\t\t\tif (!found_pack) {\n\t\t\t\tfound_offset = e.offset;\n\t\t\t\tfound_pack = e.p;\n\t\t\t}\n\t\t}\n\t}\n\n\tif (idx >= nr_alloc) {\n\t\tunsigned int needed = (idx + 1024) * 3 / 2;\n\t\tobjects = xrealloc(objects, needed * sizeof(*entry));\n\t\tnr_alloc = needed;\n\t}\n\tentry = objects + idx;\n\tmemset(entry, 0, sizeof(*entry));\n\tmemcpy(entry->sha1, sha1, 20);\n\tentry->hash = hash;\n\tif (found_pack) {\n\t\tentry->in_pack = found_pack;\n\t\tentry->in_pack_offset = found_offset;\n\t}\n\tnr_objects = idx+1;\n\treturn 1;\n}\n\nstatic int locate_object_entry_hash(unsigned char *sha1)\n{\n\tint i;\n\tunsigned int ui;\n\tmemcpy(&ui, sha1, sizeof(unsigned int));\n\ti = ui % object_ix_hashsz;\n\twhile (0 < object_ix[i]) {\n\t\tif (!memcmp(sha1, objects[object_ix[i]-1].sha1, 20))\n\t\t\treturn i;\n\t\tif (++i == object_ix_hashsz)\n\t\t\ti = 0;\n\t}\n\treturn -1 - i;\n}\n\nstatic struct object_entry *locate_object_entry(unsigned char *sha1)\n{\n\tint i = locate_object_entry_hash(sha1);\n\tif (0 <= i)\n\t\treturn &objects[object_ix[i]-1];\n\treturn NULL;\n}\n\nstatic void check_object(struct object_entry *entry)\n{\n\tchar type[20];\n\n\tif (entry->in_pack) {\n\t\tunsigned char base[20];\n\t\tunsigned long size;\n\t\tstruct object_entry *base_entry;\n\n\t\t/* We want in_pack_type even if we do not reuse delta.\n\t\t * There is no point not reusing non-delta representations.\n\t\t */\n\t\tcheck_reuse_pack_delta(entry->in_pack,\n\t\t\t\t entry->in_pack_offset,\n\t\t\t\t base, &size,\n\t\t\t\t &entry->in_pack_type);\n\n\t\t/* Check if it is delta, and the base is also an object\n\t\t * we are going to pack. If so we will reuse the existing\n\t\t * delta.\n\t\t */\n\t\tif (!no_reuse_delta &&\n\t\t entry->in_pack_type == OBJ_DELTA &&\n\t\t (base_entry = locate_object_entry(base))) {\n\n\t\t\t/* Depth value does not matter - find_deltas()\n\t\t\t * will never consider reused delta as the\n\t\t\t * base object to deltify other objects\n\t\t\t * against, in order to avoid circular deltas.\n\t\t\t */\n\n\t\t\t/* uncompressed size of the delta data */\n\t\t\tentry->size = entry->delta_size = size;\n\t\t\tentry->delta = base_entry;\n\t\t\tentry->type = OBJ_DELTA;\n\n\t\t\tentry->delta_sibling = base_entry->delta_child;\n\t\t\tbase_entry->delta_child = entry;\n\n\t\t\treturn;\n\t\t}\n\t\t/* Otherwise we would do the usual */\n\t}\n\n\tif (sha1_object_info(entry->sha1, type, &entry->size))\n\t\tdie(\"unable to get type of object %s\",\n\t\t sha1_to_hex(entry->sha1));\n\n\tif (!strcmp(type, \"commit\")) {\n\t\tentry->type = OBJ_COMMIT;\n\t} else if (!strcmp(type, \"tree\")) {\n\t\tentry->type = OBJ_TREE;\n\t} else if (!strcmp(type, \"blob\")) {\n\t\tentry->type = OBJ_BLOB;\n\t} else if (!strcmp(type, \"tag\")) {\n\t\tentry->type = OBJ_TAG;\n\t} else\n\t\tdie(\"unable to pack object %s of type %s\",\n\t\t sha1_to_hex(entry->sha1), type);\n}\n\nstatic void hash_objects(void)\n{\n\tint i;\n\tstruct object_entry *oe;\n\n\tobject_ix_hashsz = nr_objects * 2;\n\tobject_ix = xcalloc(sizeof(int), object_ix_hashsz);\n\tfor (i = 0, oe = objects; i < nr_objects; i++, oe++) {\n\t\tint ix = locate_object_entry_hash(oe->sha1);\n\t\tif (0 <= ix) {\n\t\t\terror(\"the same object '%s' added twice\",\n\t\t\t sha1_to_hex(oe->sha1));\n\t\t\tcontinue;\n\t\t}\n\t\tix = -1 - ix;\n\t\tobject_ix[ix] = i + 1;\n\t}\n}\n\nstatic unsigned int check_delta_limit(struct object_entry *me, unsigned int n)\n{\n\tstruct object_entry *child = me->delta_child;\n\tunsigned int m = n;\n\twhile (child) {\n\t\tunsigned int c = check_delta_limit(child, n + 1);\n\t\tif (m < c)\n\t\t\tm = c;\n\t\tchild = child->delta_sibling;\n\t}\n\treturn m;\n}\n\nstatic void get_object_details(void)\n{\n\tint i;\n\tstruct object_entry *entry;\n\n\thash_objects();\n\tprepare_pack_ix();\n\tfor (i = 0, entry = objects; i < nr_objects; i++, entry++)\n\t\tcheck_object(entry);\n\tfor (i = 0, entry = objects; i < nr_objects; i++, entry++)\n\t\tif (!entry->delta && entry->delta_child)\n\t\t\tentry->delta_limit =\n\t\t\t\tcheck_delta_limit(entry, 1);\n}\n\ntypedef int (*entry_sort_t)(const struct object_entry *, const struct object_entry *);\n\nstatic entry_sort_t current_sort;\n\nstatic int sort_comparator(const void *_a, const void *_b)\n{\n\tstruct object_entry *a = *(struct object_entry **)_a;\n\tstruct object_entry *b = *(struct object_entry **)_b;\n\treturn current_sort(a,b);\n}\n\nstatic struct object_entry **create_sorted_list(entry_sort_t sort)\n{\n\tstruct object_entry **list = xmalloc(nr_objects * sizeof(struct object_entry *));\n\tint i;\n\n\tfor (i = 0; i < nr_objects; i++)\n\t\tlist[i] = objects + i;\n\tcurrent_sort = sort;\n\tqsort(list, nr_objects, sizeof(struct object_entry *), sort_comparator);\n\treturn list;\n}\n\nstatic int sha1_sort(const struct object_entry *a, const struct object_entry *b)\n{\n\treturn memcmp(a->sha1, b->sha1, 20);\n}\n\nstatic int type_size_sort(const struct object_entry *a, const struct object_entry *b)\n{\n\tif (a->type < b->type)\n\t\treturn -1;\n\tif (a->type > b->type)\n\t\treturn 1;\n\tif (a->hash < b->hash)\n\t\treturn -1;\n\tif (a->hash > b->hash)\n\t\treturn 1;\n\tif (a->size < b->size)\n\t\treturn -1;\n\tif (a->size > b->size)\n\t\treturn 1;\n\treturn a < b ? -1 : (a > b);\n}\n\nstruct unpacked {\n\tstruct object_entry *entry;\n\tvoid *data;\n};\n\n/*\n * We search for deltas _backwards_ in a list sorted by type and\n * by size, so that we see progressively smaller and smaller files.\n * That's because we prefer deltas to be from the bigger file\n * to the smaller - deletes are potentially cheaper, but perhaps\n * more importantly, the bigger file is likely the more recent\n * one.\n */\nstatic int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_depth)\n{\n\tstruct object_entry *cur_entry = cur->entry;\n\tstruct object_entry *old_entry = old->entry;\n\tunsigned long size, oldsize, delta_size, sizediff;\n\tlong max_size;\n\tvoid *delta_buf;\n\n\t/* Don't bother doing diffs between different types */\n\tif (cur_entry->type != old_entry->type)\n\t\treturn -1;\n\n\t/* If the current object is at edge, take the depth the objects\n\t * that depend on the current object into account -- otherwise\n\t * they would become too deep.\n\t */\n\tif (cur_entry->delta_child) {\n\t\tif (max_depth <= cur_entry->delta_limit)\n\t\t\treturn 0;\n\t\tmax_depth -= cur_entry->delta_limit;\n\t}\n\n\tsize = cur_entry->size;\n\tif (size < 50)\n\t\treturn -1;\n\toldsize = old_entry->size;\n\tsizediff = oldsize > size ? oldsize - size : size - oldsize;\n\tif (sizediff > size / 8)\n\t\treturn -1;\n\tif (old_entry->depth >= max_depth)\n\t\treturn 0;\n\n\t/*\n\t * NOTE!\n\t *\n\t * We always delta from the bigger to the smaller, since that's\n\t * more space-efficient (deletes don't have to say _what_ they\n\t * delete).\n\t */\n\tmax_size = size / 2 - 20;\n\tif (cur_entry->delta)\n\t\tmax_size = cur_entry->delta_size-1;\n\tif (sizediff >= max_size)\n\t\treturn -1;\n\tdelta_buf = diff_delta(old->data, oldsize,\n\t\t\t cur->data, size, &delta_size, max_size);\n\tif (!delta_buf)\n\t\treturn 0;\n\tcur_entry->delta = old_entry;\n\tcur_entry->delta_size = delta_size;\n\tcur_entry->depth = old_entry->depth + 1;\n\tfree(delta_buf);\n\treturn 0;\n}\n\nstatic void progress_interval(int signum)\n{\n\tsignal(SIGALRM, progress_interval);\n\tprogress_update = 1;\n}\n\nstatic void find_deltas(struct object_entry **list, int window, int depth)\n{\n\tint i, idx;\n\tunsigned int array_size = window * sizeof(struct unpacked);\n\tstruct unpacked *array = xmalloc(array_size);\n\tunsigned processed = 0;\n\tunsigned last_percent = 999;\n\n\tmemset(array, 0, array_size);\n\ti = nr_objects;\n\tidx = 0;\n\tif (progress)\n\t\tfprintf(stderr, \"Deltifying %d objects.\\n\", nr_objects);\n\n\twhile (--i >= 0) {\n\t\tstruct object_entry *entry = list[i];\n\t\tstruct unpacked *n = array + idx;\n\t\tunsigned long size;\n\t\tchar type[10];\n\t\tint j;\n\n\t\tprocessed++;\n\t\tif (progress) {\n\t\t\tunsigned percent = processed * 100 / nr_objects;\n\t\t\tif (percent != last_percent || progress_update) {\n\t\t\t\tfprintf(stderr, \"%4u%% (%u/%u) done\\r\",\n\t\t\t\t\tpercent, processed, nr_objects);\n\t\t\t\tprogress_update = 0;\n\t\t\t\tlast_percent = percent;\n\t\t\t}\n\t\t}\n\n\t\tif (entry->delta)\n\t\t\t/* This happens if we decided to reuse existing\n\t\t\t * delta from a pack. \"!no_reuse_delta &&\" is implied.\n\t\t\t */\n\t\t\tcontinue;\n\n\t\tfree(n->data);\n\t\tn->entry = entry;\n\t\tn->data = read_sha1_file(entry->sha1, type, &size);\n\t\tif (size != entry->size)\n\t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\", sha1_to_hex(entry->sha1), size, entry->size);\n\n\t\tj = window;\n\t\twhile (--j > 0) {\n\t\t\tunsigned int other_idx = idx + j;\n\t\t\tstruct unpacked *m;\n\t\t\tif (other_idx >= window)\n\t\t\t\tother_idx -= window;\n\t\t\tm = array + other_idx;\n\t\t\tif (!m->entry)\n\t\t\t\tbreak;\n\t\t\tif (try_delta(n, m, depth) < 0)\n\t\t\t\tbreak;\n\t\t}\n\t\tidx++;\n\t\tif (idx >= window)\n\t\t\tidx = 0;\n\t}\n\n\tif (progress)\n\t\tfputc('\\n', stderr);\n\n\tfor (i = 0; i < window; ++i)\n\t\tfree(array[i].data);\n\tfree(array);\n}\n\nstatic void prepare_pack(int window, int depth)\n{\n\tget_object_details();\n\tsorted_by_type = create_sorted_list(type_size_sort);\n\tif (window && depth)\n\t\tfind_deltas(sorted_by_type, window+1, depth);\n}\n\nstatic int reuse_cached_pack(unsigned char *sha1, int pack_to_stdout)\n{\n\tstatic const char cache[] = \"pack-cache/pack-%s.%s\";\n\tchar *cached_pack, *cached_idx;\n\tint ifd, ofd, ifd_ix = -1;\n\n\tcached_pack = git_path(cache, sha1_to_hex(sha1), \"pack\");\n\tifd = open(cached_pack, O_RDONLY);\n\tif (ifd < 0)\n\t\treturn 0;\n\n\tif (!pack_to_stdout) {\n\t\tcached_idx = git_path(cache, sha1_to_hex(sha1), \"idx\");\n\t\tifd_ix = open(cached_idx, O_RDONLY);\n\t\tif (ifd_ix < 0) {\n\t\t\tclose(ifd);\n\t\t\treturn 0;\n\t\t}\n\t}\n\n\tif (progress)\n\t\tfprintf(stderr, \"Reusing %d objects pack %s\\n\", nr_objects,\n\t\t\tsha1_to_hex(sha1));\n\n\tif (pack_to_stdout) {\n\t\tif (copy_fd(ifd, 1))\n\t\t\texit(1);\n\t\tclose(ifd);\n\t}\n\telse {\n\t\tchar name[PATH_MAX];\n\t\tsnprintf(name, sizeof(name),\n\t\t\t \"%s-%s.%s\", base_name, sha1_to_hex(sha1), \"pack\");\n\t\tofd = open(name, O_CREAT | O_EXCL | O_WRONLY, 0666);\n\t\tif (ofd < 0)\n\t\t\tdie(\"unable to open %s (%s)\", name, strerror(errno));\n\t\tif (copy_fd(ifd, ofd))\n\t\t\texit(1);\n\t\tclose(ifd);\n\n\t\tsnprintf(name, sizeof(name),\n\t\t\t \"%s-%s.%s\", base_name, sha1_to_hex(sha1), \"idx\");\n\t\tofd = open(name, O_CREAT | O_EXCL | O_WRONLY, 0666);\n\t\tif (ofd < 0)\n\t\t\tdie(\"unable to open %s (%s)\", name, strerror(errno));\n\t\tif (copy_fd(ifd_ix, ofd))\n\t\t\texit(1);\n\t\tclose(ifd_ix);\n\t\tputs(sha1_to_hex(sha1));\n\t}\n\n\treturn 1;\n}\n\nint main(int argc, char **argv)\n{\n\tSHA_CTX ctx;\n\tchar line[PATH_MAX + 20];\n\tint window = 10, depth = 10, pack_to_stdout = 0;\n\tstruct object_entry **list;\n\tint i;\n\n\tsetup_git_directory();\n\n\tfor (i = 1; i < argc; i++) {\n\t\tconst char *arg = argv[i];\n\n\t\tif (*arg == '-') {\n\t\t\tif (!strcmp(\"--non-empty\", arg)) {\n\t\t\t\tnon_empty = 1;\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (!strcmp(\"--local\", arg)) {\n\t\t\t\tlocal = 1;\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (!strcmp(\"--incremental\", arg)) {\n\t\t\t\tincremental = 1;\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (!strncmp(\"--window=\", arg, 9)) {\n\t\t\t\tchar *end;\n\t\t\t\twindow = strtoul(arg+9, &end, 0);\n\t\t\t\tif (!arg[9] || *end)\n\t\t\t\t\tusage(pack_usage);\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (!strncmp(\"--depth=\", arg, 8)) {\n\t\t\t\tchar *end;\n\t\t\t\tdepth = strtoul(arg+8, &end, 0);\n\t\t\t\tif (!arg[8] || *end)\n\t\t\t\t\tusage(pack_usage);\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (!strcmp(\"-q\", arg)) {\n\t\t\t\tprogress = 0;\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (!strcmp(\"--no-reuse-delta\", arg)) {\n\t\t\t\tno_reuse_delta = 1;\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (!strcmp(\"--stdout\", arg)) {\n\t\t\t\tpack_to_stdout = 1;\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tusage(pack_usage);\n\t\t}\n\t\tif (base_name)\n\t\t\tusage(pack_usage);\n\t\tbase_name = arg;\n\t}\n\n\tif (pack_to_stdout != !base_name)\n\t\tusage(pack_usage);\n\n\tprepare_packed_git();\n\n\tif (progress) {\n\t\tstruct itimerval v;\n\t\tv.it_interval.tv_sec = 1;\n\t\tv.it_interval.tv_usec = 0;\n\t\tv.it_value = v.it_interval;\n\t\tsignal(SIGALRM, progress_interval);\n\t\tsetitimer(ITIMER_REAL, &v, NULL);\n\t\tfprintf(stderr, \"Generating pack...\\n\");\n\t}\n\n\twhile (fgets(line, sizeof(line), stdin) != NULL) {\n\t\tunsigned int hash;\n\t\tchar *p;\n\t\tunsigned char sha1[20];\n\n\t\tif (progress_update) {\n\t\t\tfprintf(stderr, \"Counting objects...%d\\r\", nr_objects);\n\t\t\tprogress_update = 0;\n\t\t}\n\t\tif (get_sha1_hex(line, sha1))\n\t\t\tdie(\"expected sha1, got garbage:\\n %s\", line);\n\t\thash = 0;\n\t\tp = line+40;\n\t\twhile (*p) {\n\t\t\tunsigned char c = *p++;\n\t\t\tif (isspace(c))\n\t\t\t\tcontinue;\n\t\t\thash = hash * 11 + c;\n\t\t}\n\t\tadd_object_entry(sha1, hash);\n\t}\n\tif (progress)\n\t\tfprintf(stderr, \"Done counting %d objects.\\n\", nr_objects);\n\tif (non_empty && !nr_objects)\n\t\treturn 0;\n\n\tsorted_by_sha = create_sorted_list(sha1_sort);\n\tSHA1_Init(&ctx);\n\tlist = sorted_by_sha;\n\tfor (i = 0; i < nr_objects; i++) {\n\t\tstruct object_entry *entry = *list++;\n\t\tSHA1_Update(&ctx, entry->sha1, 20);\n\t}\n\tSHA1_Final(object_list_sha1, &ctx);\n\n\tif (reuse_cached_pack(object_list_sha1, pack_to_stdout))\n\t\t;\n\telse {\n\t\tprepare_pack(window, depth);\n\t\tif (progress && pack_to_stdout) {\n\t\t\t/* the other end usually displays progress itself */\n\t\t\tstruct itimerval v = {{0,},};\n\t\t\tsetitimer(ITIMER_REAL, &v, NULL);\n\t\t\tsignal(SIGALRM, SIG_IGN );\n\t\t\tprogress_update = 0;\n\t\t}\n\t\twrite_pack_file();\n\t\tif (!pack_to_stdout) {\n\t\t\twrite_index_file();\n\t\t\tputs(sha1_to_hex(object_list_sha1));\n\t\t}\n\t}\n\tif (progress)\n\t\tfprintf(stderr, \"Total %d, written %d (delta %d), reused %d (delta %d)\\n\",\n\t\t\tnr_objects, written, written_delta, reused, reused_delta);\n\treturn 0;\n}\n\n\n#include \"cache.h\"\n#include \"object.h\"\n#include \"delta.h\"\n#include \"pack.h\"\n#include \"csum-file.h\"\n#include \"diff.h\"\n#include \n#include \n\nstatic const char pack_usage[] = \"git-pack-objects [-q] [--no-reuse-delta] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} < object-list\";\n\nstruct object_entry {\n\tunsigned char sha1[20];\n\tunsigned long size;\t/* uncompressed size */\n\tunsigned long offset;\t/* offset into the final pack file;\n\t\t\t\t * nonzero if already written.\n\t\t\t\t */\n\tunsigned int depth;\t/* delta depth */\n\tunsigned int delta_limit;\t/* base adjustment for in-pack delta */\n\tunsigned int hash;\t/* name hint hash */\n\tenum object_type type;\n\tenum object_type in_pack_type;\t/* could be delta */\n\tunsigned long delta_size;\t/* delta data size (uncompressed) */\n\tstruct object_entry *delta;\t/* delta base object */\n\tstruct packed_git *in_pack; \t/* already in pack */\n\tunsigned int in_pack_offset;\n\tstruct object_entry *delta_child; /* delitified objects who bases me */\n\tstruct object_entry *delta_sibling; /* other deltified objects who\n\t\t\t\t\t * uses the same base as me\n\t\t\t\t\t */\n\tint preferred_base;\t/* we do not pack this, but is encouraged to\n\t\t\t\t * be used as the base objectto delta huge\n\t\t\t\t * objects against.\n\t\t\t\t */\n\tint based_on_preferred;\t/* current delta candidate is a preferred\n\t\t\t\t * one, or delta against a preferred one.\n\t\t\t\t */\n};\n\n/*\n * Objects we are going to pack are colected in objects array (dynamically\n * expanded). nr_objects & nr_alloc controls this array. They are stored\n * in the order we see -- typically rev-list --objects order that gives us\n * nice \"minimum seek\" order.\n *\n * sorted-by-sha ans sorted-by-type are arrays of pointers that point at\n * elements in the objects array. The former is used to build the pack\n * index (lists object names in the ascending order to help offset lookup),\n * and the latter is used to group similar things together by try_delta()\n * heuristics.\n */\n\nstatic unsigned char object_list_sha1[20];\nstatic int non_empty = 0;\nstatic int no_reuse_delta = 0;\nstatic int local = 0;\nstatic int incremental = 0;\nstatic struct object_entry **sorted_by_sha, **sorted_by_type;\nstatic struct object_entry *objects = NULL;\nstatic int nr_objects = 0, nr_alloc = 0, nr_result = 0;\nstatic const char *base_name;\nstatic unsigned char pack_file_sha1[20];\nstatic int progress = 1;\nstatic volatile int progress_update = 0;\n\n/*\n * The object names in objects array are hashed with this hashtable,\n * to help looking up the entry by object name. Binary search from\n * sorted_by_sha is also possible but this was easier to code and faster.\n * This hashtable is built after all the objects are seen.\n */\nstatic int *object_ix = NULL;\nstatic int object_ix_hashsz = 0;\n\n/*\n * Pack index for existing packs give us easy access to the offsets into\n * corresponding pack file where each object's data starts, but the entries\n * do not store the size of the compressed representation (uncompressed\n * size is easily available by examining the pack entry header). We build\n * a hashtable of existing packs (pack_revindex), and keep reverse index\n * here -- pack index file is sorted by object name mapping to offset; this\n * pack_revindex[].revindex array is an ordered list of offsets, so if you\n * know the offset of an object, next offset is where its packed\n * representation ends.\n */\nstruct pack_revindex {\n\tstruct packed_git *p;\n\tunsigned long *revindex;\n} *pack_revindex = NULL;\nstatic int pack_revindex_hashsz = 0;\n\n/*\n * stats\n */\nstatic int written = 0;\nstatic int written_delta = 0;\nstatic int reused = 0;\nstatic int reused_delta = 0;\n\nstatic int pack_revindex_ix(struct packed_git *p)\n{\n\tunsigned int ui = (unsigned int) p;\n\tint i;\n\n\tui = ui ^ (ui >> 16); /* defeat structure alignment */\n\ti = (int)(ui % pack_revindex_hashsz);\n\twhile (pack_revindex[i].p) {\n\t\tif (pack_revindex[i].p == p)\n\t\t\treturn i;\n\t\tif (++i == pack_revindex_hashsz)\n\t\t\ti = 0;\n\t}\n\treturn -1 - i;\n}\n\nstatic void prepare_pack_ix(void)\n{\n\tint num;\n\tstruct packed_git *p;\n\tfor (num = 0, p = packed_git; p; p = p->next)\n\t\tnum++;\n\tif (!num)\n\t\treturn;\n\tpack_revindex_hashsz = num * 11;\n\tpack_revindex = xcalloc(sizeof(*pack_revindex), pack_revindex_hashsz);\n\tfor (p = packed_git; p; p = p->next) {\n\t\tnum = pack_revindex_ix(p);\n\t\tnum = - 1 - num;\n\t\tpack_revindex[num].p = p;\n\t}\n\t/* revindex elements are lazily initialized */\n}\n\nstatic int cmp_offset(const void *a_, const void *b_)\n{\n\tunsigned long a = *(unsigned long *) a_;\n\tunsigned long b = *(unsigned long *) b_;\n\tif (a < b)\n\t\treturn -1;\n\telse if (a == b)\n\t\treturn 0;\n\telse\n\t\treturn 1;\n}\n\n/*\n * Ordered list of offsets of objects in the pack.\n */\nstatic void prepare_pack_revindex(struct pack_revindex *rix)\n{\n\tstruct packed_git *p = rix->p;\n\tint num_ent = num_packed_objects(p);\n\tint i;\n\tvoid *index = p->index_base + 256;\n\n\trix->revindex = xmalloc(sizeof(unsigned long) * (num_ent + 1));\n\tfor (i = 0; i < num_ent; i++) {\n\t\tlong hl = *((long *)(index + 24 * i));\n\t\trix->revindex[i] = ntohl(hl);\n\t}\n\t/* This knows the pack format -- the 20-byte trailer\n\t * follows immediately after the last object data.\n\t */\n\trix->revindex[num_ent] = p->pack_size - 20;\n\tqsort(rix->revindex, num_ent, sizeof(unsigned long), cmp_offset);\n}\n\nstatic unsigned long find_packed_object_size(struct packed_git *p,\n\t\t\t\t\t unsigned long ofs)\n{\n\tint num;\n\tint lo, hi;\n\tstruct pack_revindex *rix;\n\tunsigned long *revindex;\n\tnum = pack_revindex_ix(p);\n\tif (num < 0)\n\t\tdie(\"internal error: pack revindex uninitialized\");\n\trix = &pack_revindex[num];\n\tif (!rix->revindex)\n\t\tprepare_pack_revindex(rix);\n\trevindex = rix->revindex;\n\tlo = 0;\n\thi = num_packed_objects(p) + 1;\n\tdo {\n\t\tint mi = (lo + hi) / 2;\n\t\tif (revindex[mi] == ofs) {\n\t\t\treturn revindex[mi+1] - ofs;\n\t\t}\n\t\telse if (ofs < revindex[mi])\n\t\t\thi = mi;\n\t\telse\n\t\t\tlo = mi + 1;\n\t} while (lo < hi);\n\tdie(\"internal error: pack revindex corrupt\");\n}\n\nstatic void *delta_against(void *buf, unsigned long size, struct object_entry *entry)\n{\n\tunsigned long othersize, delta_size;\n\tchar type[10];\n\tvoid *otherbuf = read_sha1_file(entry->delta->sha1, type, &othersize);\n\tvoid *delta_buf;\n\n\tif (!otherbuf)\n\t\tdie(\"unable to read %s\", sha1_to_hex(entry->delta->sha1));\n delta_buf = diff_delta(otherbuf, othersize,\n\t\t\t buf, size, &delta_size, 0);\n if (!delta_buf || delta_size != entry->delta_size)\n \tdie(\"delta size changed\");\n free(buf);\n free(otherbuf);\n\treturn delta_buf;\n}\n\n/*\n * The per-object header is a pretty dense thing, which is\n * - first byte: low four bits are \"size\", then three bits of \"type\",\n * and the high bit is \"size continues\".\n * - each byte afterwards: low seven bits are size continuation,\n * with the high bit being \"size continues\"\n */\nstatic int encode_header(enum object_type type, unsigned long size, unsigned char *hdr)\n{\n\tint n = 1;\n\tunsigned char c;\n\n\tif (type < OBJ_COMMIT || type > OBJ_DELTA)\n\t\tdie(\"bad type %d\", type);\n\n\tc = (type << 4) | (size & 15);\n\tsize >>= 4;\n\twhile (size) {\n\t\t*hdr++ = c | 0x80;\n\t\tc = size & 0x7f;\n\t\tsize >>= 7;\n\t\tn++;\n\t}\n\t*hdr = c;\n\treturn n;\n}\n\nstatic unsigned long write_object(struct sha1file *f,\n\t\t\t\t struct object_entry *entry)\n{\n\tunsigned long size;\n\tchar type[10];\n\tvoid *buf;\n\tunsigned char header[10];\n\tunsigned hdrlen, datalen;\n\tenum object_type obj_type;\n\tint to_reuse = 0;\n\n\tif (entry->preferred_base)\n\t\treturn 0;\n\n\tobj_type = entry->type;\n\tif (! entry->in_pack)\n\t\tto_reuse = 0;\t/* can't reuse what we don't have */\n\telse if (obj_type == OBJ_DELTA)\n\t\tto_reuse = 1;\t/* check_object() decided it for us */\n\telse if (obj_type != entry->in_pack_type)\n\t\tto_reuse = 0;\t/* pack has delta which is unusable */\n\telse if (entry->delta)\n\t\tto_reuse = 0;\t/* we want to pack afresh */\n\telse\n\t\tto_reuse = 1;\t/* we have it in-pack undeltified,\n\t\t\t\t * and we do not need to deltify it.\n\t\t\t\t */\n\n\tif (! to_reuse) {\n\t\tbuf = read_sha1_file(entry->sha1, type, &size);\n\t\tif (!buf)\n\t\t\tdie(\"unable to read %s\", sha1_to_hex(entry->sha1));\n\t\tif (size != entry->size)\n\t\t\tdie(\"object %s size inconsistency (%lu vs %lu)\",\n\t\t\t sha1_to_hex(entry->sha1), size, entry->size);\n\t\tif (entry->delta) {\n\t\t\tbuf = delta_against(buf, size, entry);\n\t\t\tsize = entry->delta_size;\n\t\t\tobj_type = OBJ_DELTA;\n\t\t}\n\t\t/*\n\t\t * The object header is a byte of 'type' followed by zero or\n\t\t * more bytes of length. For deltas, the 20 bytes of delta\n\t\t * sha1 follows that.\n\t\t */\n\t\thdrlen = encode_header(obj_type, size, header);\n\t\tsha1write(f, header, hdrlen);\n\n\t\tif (entry->delta) {\n\t\t\tsha1write(f, entry->delta, 20);\n\t\t\thdrlen += 20;\n\t\t}\n\t\tdatalen = sha1write_compressed(f, buf, size);\n\t\tfree(buf);\n\t}\n\telse {\n\t\tstruct packed_git *p = entry->in_pack;\n\t\tuse_packed_git(p);\n\n\t\tdatalen = find_packed_object_size(p, entry->in_pack_offset);\n\t\tbuf = p->pack_base + entry->in_pack_offset;\n\t\tsha1write(f, buf, datalen);\n\t\tunuse_packed_git(p);\n\t\thdrlen = 0; /* not really */\n\t\tif (obj_type == OBJ_DELTA)\n\t\t\treused_delta++;\n\t\treused++;\n\t}\n\tif (obj_type == OBJ_DELTA)\n\t\twritten_delta++;\n\twritten++;\n\treturn hdrlen + datalen;\n}\n\nstatic unsigned long write_one(struct sha1file *f,\n\t\t\t struct object_entry *e,\n\t\t\t unsigned long offset)\n{\n\tif (e->offset)\n\t\t/* offset starts from header size and cannot be zero\n\t\t * if it is written already.\n\t\t */\n\t\treturn offset;\n\te->offset = offset;\n\toffset += write_object(f, e);\n\t/* if we are deltified, write out its base object. */\n\tif (e->delta)\n\t\toffset = write_one(f, e->delta, offset);\n\treturn offset;\n}\n\nstatic void write_pack_file(void)\n{\n\tint i;\n\tstruct sha1file *f;\n\tunsigned long offset;\n\tstruct pack_header hdr;\n\tunsigned last_percent = 999;\n\tint do_progress = 0;\n\n\tif (!base_name)\n\t\tf = sha1fd(1, \"\");\n\telse {\n\t\tf = sha1create(\"%s-%s.%s\", base_name,\n\t\t\t sha1_to_hex(object_list_sha1), \"pack\");\n\t\tdo_progress = progress;\n\t}\n\tif (do_progress)\n\t\tfprintf(stderr, \"Writing %d objects.\\n\", nr_result);\n\n\thdr.hdr_signature = htonl(PACK_SIGNATURE);\n\thdr.hdr_version = htonl(PACK_VERSION);\n\thdr.hdr_entries = htonl(nr_result);\n\tsha1write(f, &hdr, sizeof(hdr));\n\toffset = sizeof(hdr);\n\tif (!nr_result)\n\t\tgoto done;\n\tfor (i = 0; i < nr_objects; i++) {\n\t\toffset = write_one(f, objects + i, offset);\n\t\tif (do_progress) {\n\t\t\tunsigned percent = written * 100 / nr_result;\n\t\t\tif (progress_update || percent != last_percent) {\n\t\t\t\tfprintf(stderr, \"%4u%% (%u/%u) done\\r\",\n\t\t\t\t\tpercent, written, nr_result);\n\t\t\t\tprogress_update = 0;\n\t\t\t\tlast_percent = percent;\n\t\t\t}\n\t\t}\n\t}\n\tif (do_progress)\n\t\tfputc('\\n', stderr);\n done:\n\tsha1close(f, pack_file_sha1, 1);\n}\n\nstatic void write_index_file(void)\n{\n\tint i;\n\tstruct sha1file *f = sha1create(\"%s-%s.%s\", base_name,\n\t\t\t\t\tsha1_to_hex(object_list_sha1), \"idx\");\n\tstruct object_entry **list = sorted_by_sha;\n\tstruct object_entry **last = list + nr_result;\n\tunsigned int array[256];\n\n\t/*\n\t * Write the first-level table (the list is sorted,\n\t * but we use a 256-entry lookup to be able to avoid\n\t * having to do eight extra binary search iterations).\n\t */\n\tfor (i = 0; i < 256; i++) {\n\t\tstruct object_entry **next = list;\n\t\twhile (next < last) {\n\t\t\tstruct object_entry *entry = *next;\n\t\t\tif (entry->sha1[0] != i)\n\t\t\t\tbreak;\n\t\t\tnext++;\n\t\t}\n\t\tarray[i] = htonl(next - sorted_by_sha);\n\t\tlist = next;\n\t}\n\tsha1write(f, array, 256 * sizeof(int));\n\n\t/*\n\t * Write the actual SHA1 entries..\n\t */\n\tlist = sorted_by_sha;\n\tfor (i = 0; i < nr_result; i++) {\n\t\tstruct object_entry *entry = *list++;\n\t\tunsigned int offset = htonl(entry->offset);\n\t\tsha1write(f, &offset, 4);\n\t\tsha1write(f, entry->sha1, 20);\n\t}\n\tsha1write(f, pack_file_sha1, 20);\n\tsha1close(f, NULL, 1);\n}\n\nstatic int locate_object_entry_hash(const unsigned char *sha1)\n{\n\tint i;\n\tunsigned int ui;\n\tmemcpy(&ui, sha1, sizeof(unsigned int));\n\ti = ui % object_ix_hashsz;\n\twhile (0 < object_ix[i]) {\n\t\tif (!memcmp(sha1, objects[object_ix[i]-1].sha1, 20))\n\t\t\treturn i;\n\t\tif (++i == object_ix_hashsz)\n\t\t\ti = 0;\n\t}\n\treturn -1 - i;\n}\n\nstatic struct object_entry *locate_object_entry(const unsigned char *sha1)\n{\n\tint i;\n\n\tif (!object_ix_hashsz)\n\t\treturn NULL;\n\n\ti = locate_object_entry_hash(sha1);\n\tif (0 <= i)\n\t\treturn &objects[object_ix[i]-1];\n\treturn NULL;\n}\n\nstatic void rehash_objects(void)\n{\n\tint i;\n\tstruct object_entry *oe;\n\n\tobject_ix_hashsz = nr_objects * 3;\n\tif (object_ix_hashsz < 1024)\n\t\tobject_ix_hashsz = 1024;\n\tobject_ix = xrealloc(object_ix, sizeof(int) * object_ix_hashsz);\n\tobject_ix = memset(object_ix, 0, sizeof(int) * object_ix_hashsz);\n\tfor (i = 0, oe = objects; i < nr_objects; i++, oe++) {\n\t\tint ix = locate_object_entry_hash(oe->sha1);\n\t\tif (0 <= ix)\n\t\t\tcontinue;\n\t\tix = -1 - ix;\n\t\tobject_ix[ix] = i + 1;\n\t}\n}\n\nstruct name_path {\n\tstruct name_path *up;\n\tconst char *elem;\n\tint len;\n};\n\n#define DIRBITS 12\n\nstatic unsigned name_hash(struct name_path *path, const char *name)\n{\n\tstruct name_path *p = path;\n\tconst char *n = name + strlen(name);\n\tunsigned hash = 0, name_hash = 0, name_done = 0;\n\n\tif (n != name && n[-1] == '\\n')\n\t\tn--;\n\twhile (name <= --n) {\n\t\tunsigned char c = *n;\n\t\tif (c == '/' && !name_done) {\n\t\t\tname_hash = hash;\n\t\t\tname_done = 1;\n\t\t\thash = 0;\n\t\t}\n\t\thash = hash * 11 + c;\n\t}\n\tif (!name_done) {\n\t\tname_hash = hash;\n\t\thash = 0;\n\t}\n\tfor (p = path; p; p = p->up) {\n\t\thash = hash * 11 + '/';\n\t\tn = p->elem + p->len;\n\t\twhile (p->elem <= --n) {\n\t\t\tunsigned char c = *n;\n\t\t\thash = hash * 11 + c;\n\t\t}\n\t}\n\t/*\n\t * Make sure \"Makefile\" and \"t/Makefile\" are hashed separately\n\t * but close enough.\n\t */\n\thash = (name_hash<up) {\n\t\t\tfputc('/', stderr);\n\t\t\tn = p->elem + p->len;\n\t\t\twhile (p->elem <= --n)\n\t\t\t\tfputc(*n, stderr);\n\t\t}\n\t\tfprintf(stderr, \"\\t%08x\\n\", hash);\n\t}\n\treturn hash;\n}\n\nstatic int add_object_entry(const unsigned char *sha1, unsigned hash, int exclude)\n{\n\tunsigned int idx = nr_objects;\n\tstruct object_entry *entry;\n\tstruct packed_git *p;\n\tunsigned int found_offset = 0;\n\tstruct packed_git *found_pack = NULL;\n\tint ix, status = 0;\n\n\tif (!exclude) {\n\t\tfor (p = packed_git; p; p = p->next) {\n\t\t\tstruct pack_entry e;\n\t\t\tif (find_pack_entry_one(sha1, &e, p)) {\n\t\t\t\tif (incremental)\n\t\t\t\t\treturn 0;\n\t\t\t\tif (local && !p->pack_local)\n\t\t\t\t\treturn 0;\n\t\t\t\tif (!found_pack) {\n\t\t\t\t\tfound_offset = e.offset;\n\t\t\t\t\tfound_pack = e.p;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tif ((entry = locate_object_entry(sha1)) != NULL)\n\t\tgoto already_added;\n\n\tif (idx >= nr_alloc) {\n\t\tunsigned int needed = (idx + 1024) * 3 / 2;\n\t\tobjects = xrealloc(objects, needed * sizeof(*entry));\n\t\tnr_alloc = needed;\n\t}\n\tentry = objects + idx;\n\tnr_objects = idx + 1;\n\tmemset(entry, 0, sizeof(*entry));\n\tmemcpy(entry->sha1, sha1, 20);\n\tentry->hash = hash;\n\n\tif (object_ix_hashsz * 3 <= nr_objects * 4)\n\t\trehash_objects();\n\telse {\n\t\tix = locate_object_entry_hash(entry->sha1);\n\t\tif (0 <= ix)\n\t\t\tdie(\"internal error in object hashing.\");\n\t\tobject_ix[-1 - ix] = idx + 1;\n\t}\n\tstatus = 1;\n\n already_added:\n\tif (progress_update) {\n\t\tfprintf(stderr, \"Counting objects...%d\\r\", nr_objects);\n\t\tprogress_update = 0;\n\t}\n\tif (exclude)\n\t\tentry->preferred_base = 1;\n\telse {\n\t\tif (found_pack) {\n\t\t\tentry->in_pack = found_pack;\n\t\t\tentry->in_pack_offset = found_offset;\n\t\t}\n\t}\n\treturn status;\n}\n\nstatic void add_pbase_tree(struct tree_desc *tree, struct name_path *up)\n{\n\twhile (tree->size) {\n\t\tconst unsigned char *sha1;\n\t\tconst char *name;\n\t\tunsigned mode, hash;\n\t\tunsigned long size;\n\t\tchar type[20];\n\n\t\tsha1 = tree_entry_extract(tree, &name, &mode);\n\t\tupdate_tree_entry(tree);\n\t\tif (!has_sha1_file(sha1))\n\t\t\tcontinue;\n\t\tif (sha1_object_info(sha1, type, &size))\n\t\t\tcontinue;\n\n\t\thash = name_hash(up, name);\n\t\tif (!add_object_entry(sha1, hash, 1))\n\t\t\tcontinue;\n\n\t\tif (!strcmp(type, \"tree\")) {\n\t\t\tstruct tree_desc sub;\n\t\t\tvoid *elem;\n\t\t\tstruct name_path me;\n\n\t\t\telem = read_sha1_file(sha1, type, &sub.size);\n\t\t\tsub.buf = elem;\n\t\t\tif (sub.buf) {\n\t\t\t\tme.up = up;\n\t\t\t\tme.elem = name;\n\t\t\t\tme.len = strlen(name);\n\t\t\t\tadd_pbase_tree(&sub, &me);\n\t\t\t\tfree(elem);\n\t\t\t}\n\t\t}\n\t}\n}\n\nstatic void add_preferred_base(unsigned char *sha1)\n{\n\tstruct tree_desc tree;\n\tvoid *elem;\n\n\telem = read_object_with_reference(sha1, \"tree\", &tree.size, NULL);\n\ttree.buf = elem;\n\tif (!tree.buf)\n\t\treturn;\n\tif (add_object_entry(sha1, name_hash(NULL, \"\"), 1))\n\t\tadd_pbase_tree(&tree, NULL);\n\tfree(elem);\n}\n\nstatic void check_object(struct object_entry *entry)\n{\n\tchar type[20];\n\n\tif (entry->in_pack && !entry->preferred_base) {\n\t\tunsigned char base[20];\n\t\tunsigned long size;\n\t\tstruct object_entry *base_entry;\n\n\t\t/* We want in_pack_type even if we do not reuse delta.\n\t\t * There is no point not reusing non-delta representations.\n\t\t */\n\t\tcheck_reuse_pack_delta(entry->in_pack,\n\t\t\t\t entry->in_pack_offset,\n\t\t\t\t base, &size,\n\t\t\t\t &entry->in_pack_type);\n\n\t\t/* Check if it is delta, and the base is also an object\n\t\t * we are going to pack. If so we will reuse the existing\n\t\t * delta.\n\t\t */\n\t\tif (!no_reuse_delta &&\n\t\t entry->in_pack_type == OBJ_DELTA &&\n\t\t (base_entry = locate_object_entry(base)) &&\n\t\t (!base_entry->preferred_base)) {\n\n\t\t\t/* Depth value does not matter - find_deltas()\n\t\t\t * will never consider reused delta as the\n\t\t\t * base object to deltify other objects\n\t\t\t * against, in order to avoid circular deltas.\n\t\t\t */\n\n\t\t\t/* uncompressed size of the delta data */\n\t\t\tentry->size = entry->delta_size = size;\n\t\t\tentry->delta = base_entry;\n\t\t\tentry->type = OBJ_DELTA;\n\n\t\t\tentry->delta_sibling = base_entry->delta_child;\n\t\t\tbase_entry->delta_child = entry;\n\n\t\t\treturn;\n\t\t}\n\t\t/* Otherwise we would do the usual */\n\t}\n\n\tif (sha1_object_info(entry->sha1, type, &entry->size))\n\t\tdie(\"unable to get type of object %s\",\n\t\t sha1_to_hex(entry->sha1));\n\n\tif (!strcmp(type, \"commit\")) {\n\t\tentry->type = OBJ_COMMIT;\n\t} else if (!strcmp(type, \"tree\")) {\n\t\tentry->type = OBJ_TREE;\n\t} else if (!strcmp(type, \"blob\")) {\n\t\tentry->type = OBJ_BLOB;\n\t} else if (!strcmp(type, \"tag\")) {\n\t\tentry->type = OBJ_TAG;\n\t} else\n\t\tdie(\"unable to pack object %s of type %s\",\n\t\t sha1_to_hex(entry->sha1), type);\n}\n\nstatic unsigned int check_delta_limit(struct object_entry *me, unsigned int n)\n{\n\tstruct object_entry *child = me->delta_child;\n\tunsigned int m = n;\n\twhile (child) {\n\t\tunsigned int c = check_delta_limit(child, n + 1);\n\t\tif (m < c)\n\t\t\tm = c;\n\t\tchild = child->delta_sibling;\n\t}\n\treturn m;\n}\n\nstatic void get_object_details(void)\n{\n\tint i;\n\tstruct object_entry *entry;\n\n\tprepare_pack_ix();\n\tfor (i = 0, entry = objects; i < nr_objects; i++, entry++)\n\t\tcheck_object(entry);\n\n\tif (nr_objects == nr_result) {\n\t\t/*\n\t\t * Depth of objects that depend on the entry -- this\n\t\t * is subtracted from depth-max to break too deep\n\t\t * delta chain because of delta data reusing.\n\t\t * However, we loosen this restriction when we know we\n\t\t * are creating a thin pack -- it will have to be\n\t\t * expanded on the other end anyway, so do not\n\t\t * artificially cut the delta chain and let it go as\n\t\t * deep as it wants.\n\t\t */\n\t\tfor (i = 0, entry = objects; i < nr_objects; i++, entry++)\n\t\t\tif (!entry->delta && entry->delta_child)\n\t\t\t\tentry->delta_limit =\n\t\t\t\t\tcheck_delta_limit(entry, 1);\n\t}\n}\n\ntypedef int (*entry_sort_t)(const struct object_entry *, const struct object_entry *);\n\nstatic entry_sort_t current_sort;\n\nstatic int sort_comparator(const void *_a, const void *_b)\n{\n\tstruct object_entry *a = *(struct object_entry **)_a;\n\tstruct object_entry *b = *(struct object_entry **)_b;\n\treturn current_sort(a,b);\n}\n\nstatic struct object_entry **create_sorted_list(entry_sort_t sort)\n{\n\tstruct object_entry **list = xmalloc(nr_objects * sizeof(struct object_entry *));\n\tint i;\n\n\tfor (i = 0; i < nr_objects; i++)\n\t\tlist[i] = objects + i;\n\tcurrent_sort = sort;\n\tqsort(list, nr_objects, sizeof(struct object_entry *), sort_comparator);\n\treturn list;\n}\n\nstatic int sha1_sort(const struct object_entry *a, const struct object_entry *b)\n{\n\treturn memcmp(a->sha1, b->sha1, 20);\n}\n\nstatic struct object_entry **create_final_object_list()\n{\n\tstruct object_entry **list;\n\tint i, j;\n\n\tfor (i = nr_result = 0; i < nr_objects; i++)\n\t\tif (!objects[i].preferred_base)\n\t\t\tnr_result++;\n\tlist = xmalloc(nr_result * sizeof(struct object_entry *));\n\tfor (i = j = 0; i < nr_objects; i++) {\n\t\tif (!objects[i].preferred_base)\n\t\t\tlist[j++] = objects + i;\n\t}\n\tcurrent_sort = sha1_sort;\n\tqsort(list, nr_result, sizeof(struct object_entry *), sort_comparator);\n\treturn list;\n}\n\nstatic int type_size_sort(const struct object_entry *a, const struct object_entry *b)\n{\n\tif (a->type < b->type)\n\t\treturn -1;\n\tif (a->type > b->type)\n\t\treturn 1;\n\tif (a->hash < b->hash)\n\t\treturn -1;\n\tif (a->hash > b->hash)\n\t\treturn 1;\n\tif (a->preferred_base < b->preferred_base)\n\t\treturn -1;\n\tif (a->preferred_base > b->preferred_base)\n\t\treturn 1;\n\tif (a->size < b->size)\n\t\treturn -1;\n\tif (a->size > b->size)\n\t\treturn 1;\n\treturn a < b ? -1 : (a > b);\n}\n\nstruct unpacked {\n\tstruct object_entry *entry;\n\tvoid *data;\n};\n\n/*\n * We search for deltas _backwards_ in a list sorted by type and\n * by size, so that we see progressively smaller and smaller files.\n * That's because we prefer deltas to be from the bigger file\n * to the smaller - deletes are potentially cheaper, but perhaps\n * more importantly, the bigger file is likely the more recent\n * one.\n */\nstatic int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_depth)\n{\n\tstruct object_entry *cur_entry = cur->entry;\n\tstruct object_entry *old_entry = old->entry;\n\tint old_preferred = (old_entry->preferred_base ||\n\t\t\t old_entry->based_on_preferred);\n\tunsigned long size, oldsize, delta_size, sizediff;\n\tlong max_size;\n\tvoid *delta_buf;\n\n\t/* Don't bother doing diffs between different types */\n\tif (cur_entry->type != old_entry->type)\n\t\treturn -1;\n\n\t/* We do not compute delta to *create* objects we are not\n\t * going to pack.\n\t */\n\tif (cur_entry->preferred_base)\n\t\treturn -1;\n\n\t/* If the current object is at pack edge, take the depth the\n\t * objects that depend on the current object into account --\n\t * otherwise they would become too deep.\n\t */\n\tif (cur_entry->delta_child) {\n\t\tif (max_depth <= cur_entry->delta_limit)\n\t\t\treturn 0;\n\t\tmax_depth -= cur_entry->delta_limit;\n\t}\n\n\tsize = cur_entry->size;\n\tif (size < 50)\n\t\treturn -1;\n\toldsize = old_entry->size;\n\tsizediff = oldsize > size ? oldsize - size : size - oldsize;\n\tif (sizediff > size / 8)\n\t\treturn -1;\n\tif (old_entry->depth >= max_depth)\n\t\treturn 0;\n\n\t/*\n\t * NOTE!\n\t *\n\t * We always delta from the bigger to the smaller, since that's\n\t * more space-efficient (deletes don't have to say _what_ they\n\t * delete).\n\t */\n\tmax_size = size / 2 - 20;\n\tif (cur_entry->delta) {\n\t\tif (cur_entry->based_on_preferred) {\n\t\t\tif (old_preferred)\n\t\t\t\tmax_size = cur_entry->delta_size-1;\n\t\t\telse\n\t\t\t\t/* trying with non-preferred one when we\n\t\t\t\t * already have a delta based on preferred\n\t\t\t\t * one is pointless.\n\t\t\t\t */\n\t\t\t\treturn -1;\n\t\t}\n\t\telse if (!old_preferred)\n\t\t\tmax_size = cur_entry->delta_size-1;\n\t\telse\n\t\t\t/* otherwise... even if delta with a\n\t\t\t * preferred one produces a bigger result than\n\t\t\t * what we currently have, which is based on a\n\t\t\t * non-preferred one, it is OK.\n\t\t\t */\n\t\t\t;\n\t}\n\tif (sizediff >= max_size)\n\t\treturn -1;\n\tdelta_buf = diff_delta(old->data, oldsize,\n\t\t\t cur->data, size, &delta_size, max_size);\n\tif (!delta_buf)\n\t\treturn 0;\n\tcur_entry->delta = old_entry;\n\tcur_entry->delta_size = delta_size;\n\tcur_entry->depth = old_entry->depth + 1;\n\tcur_entry->based_on_preferred = old_preferred;\n\tfree(delta_buf);\n\treturn 0;\n}\n\nstatic void progress_interval(int signum)\n{\n\tsignal(SIGALRM, progress_interval);\n\tprogress_update = 1;\n}\n\nstatic void find_deltas(struct object_entry **list, int window, int depth)\n{\n\tint i, idx;\n\tunsigned int array_size = window * sizeof(struct unpacked);\n\tstruct unpacked *array = xmalloc(array_size);\n\tunsigned processed = 0;\n\tunsigned last_percent = 999;\n\n\tmemset(array, 0, array_size);\n\ti = nr_objects;\n\tidx = 0;\n\tif (progress)\n\t\tfprintf(stderr, \"Deltifying %d objects.\\n\", nr_result);\n\n\twhile (--i >= 0) {\n\t\tstruct object_entry *entry = list[i];\n\t\tstruct unpacked *n = array + idx;\n\t\tunsigned long size;\n\t\tchar type[10];\n\t\tint j;\n\n\t\tif (!entry->preferred_base)\n\t\t\tprocessed++;\n\n\t\tif (progress) {\n\t\t\tunsigned percent = processed * 100 / nr_result;\n\t\t\tif (percent != last_percent || progress_update) {\n\t\t\t\tfprintf(stderr, \"%4u%% (%u/%u) done\\r\",\n\t\t\t\t\tpercent, processed, nr_result);\n\t\t\t\tprogress_update = 0;\n\t\t\t\tlast_percent = percent;\n\t\t\t}\n\t\t}\n\n\t\tif (entry->delta)\n\t\t\t/* This happens if we decided to reuse existing\n\t\t\t * delta from a pack. \"!no_reuse_delta &&\" is implied.\n\t\t\t */\n\t\t\tcontinue;\n\n\t\tfree(n->data);\n\t\tn->entry = entry;\n\t\tn->data = read_sha1_file(entry->sha1, type, &size);\n\t\tif (size != entry->size)\n\t\t\tdie(\"object %s inconsistent object length (%lu vs %lu)\", sha1_to_hex(entry->sha1), size, entry->size);\n\n\t\tj = window;\n\t\twhile (--j > 0) {\n\t\t\tunsigned int other_idx = idx + j;\n\t\t\tstruct unpacked *m;\n\t\t\tif (other_idx >= window)\n\t\t\t\tother_idx -= window;\n\t\t\tm = array + other_idx;\n\t\t\tif (!m->entry)\n\t\t\t\tbreak;\n\t\t\tif (try_delta(n, m, depth) < 0)\n\t\t\t\tbreak;\n\t\t}\n\t\tidx++;\n\t\tif (idx >= window)\n\t\t\tidx = 0;\n\t}\n\n\tif (progress)\n\t\tfputc('\\n', stderr);\n\n\tfor (i = 0; i < window; ++i)\n\t\tfree(array[i].data);\n\tfree(array);\n}\n\nstatic void prepare_pack(int window, int depth)\n{\n\tget_object_details();\n\tsorted_by_type = create_sorted_list(type_size_sort);\n\tif (window && depth)\n\t\tfind_deltas(sorted_by_type, window+1, depth);\n}\n\nstatic int reuse_cached_pack(unsigned char *sha1, int pack_to_stdout)\n{\n\tstatic const char cache[] = \"pack-cache/pack-%s.%s\";\n\tchar *cached_pack, *cached_idx;\n\tint ifd, ofd, ifd_ix = -1;\n\n\tcached_pack = git_path(cache, sha1_to_hex(sha1), \"pack\");\n\tifd = open(cached_pack, O_RDONLY);\n\tif (ifd < 0)\n\t\treturn 0;\n\n\tif (!pack_to_stdout) {\n\t\tcached_idx = git_path(cache, sha1_to_hex(sha1), \"idx\");\n\t\tifd_ix = open(cached_idx, O_RDONLY);\n\t\tif (ifd_ix < 0) {\n\t\t\tclose(ifd);\n\t\t\treturn 0;\n\t\t}\n\t}\n\n\tif (progress)\n\t\tfprintf(stderr, \"Reusing %d objects pack %s\\n\", nr_objects,\n\t\t\tsha1_to_hex(sha1));\n\n\tif (pack_to_stdout) {\n\t\tif (copy_fd(ifd, 1))\n\t\t\texit(1);\n\t\tclose(ifd);\n\t}\n\telse {\n\t\tchar name[PATH_MAX];\n\t\tsnprintf(name, sizeof(name),\n\t\t\t \"%s-%s.%s\", base_name, sha1_to_hex(sha1), \"pack\");\n\t\tofd = open(name, O_CREAT | O_EXCL | O_WRONLY, 0666);\n\t\tif (ofd < 0)\n\t\t\tdie(\"unable to open %s (%s)\", name, strerror(errno));\n\t\tif (copy_fd(ifd, ofd))\n\t\t\texit(1);\n\t\tclose(ifd);\n\n\t\tsnprintf(name, sizeof(name),\n\t\t\t \"%s-%s.%s\", base_name, sha1_to_hex(sha1), \"idx\");\n\t\tofd = open(name, O_CREAT | O_EXCL | O_WRONLY, 0666);\n\t\tif (ofd < 0)\n\t\t\tdie(\"unable to open %s (%s)\", name, strerror(errno));\n\t\tif (copy_fd(ifd_ix, ofd))\n\t\t\texit(1);\n\t\tclose(ifd_ix);\n\t\tputs(sha1_to_hex(sha1));\n\t}\n\n\treturn 1;\n}\n\nint main(int argc, char **argv)\n{\n\tSHA_CTX ctx;\n\tchar line[PATH_MAX + 20];\n\tint window = 10, depth = 10, pack_to_stdout = 0;\n\tstruct object_entry **list;\n\tint i;\n\n\tsetup_git_directory();\n\n\tfor (i = 1; i < argc; i++) {\n\t\tconst char *arg = argv[i];\n\n\t\tif (*arg == '-') {\n\t\t\tif (!strcmp(\"--non-empty\", arg)) {\n\t\t\t\tnon_empty = 1;\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (!strcmp(\"--local\", arg)) {\n\t\t\t\tlocal = 1;\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (!strcmp(\"--incremental\", arg)) {\n\t\t\t\tincremental = 1;\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (!strncmp(\"--window=\", arg, 9)) {\n\t\t\t\tchar *end;\n\t\t\t\twindow = strtoul(arg+9, &end, 0);\n\t\t\t\tif (!arg[9] || *end)\n\t\t\t\t\tusage(pack_usage);\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (!strncmp(\"--depth=\", arg, 8)) {\n\t\t\t\tchar *end;\n\t\t\t\tdepth = strtoul(arg+8, &end, 0);\n\t\t\t\tif (!arg[8] || *end)\n\t\t\t\t\tusage(pack_usage);\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (!strcmp(\"-q\", arg)) {\n\t\t\t\tprogress = 0;\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (!strcmp(\"--no-reuse-delta\", arg)) {\n\t\t\t\tno_reuse_delta = 1;\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (!strcmp(\"--stdout\", arg)) {\n\t\t\t\tpack_to_stdout = 1;\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tusage(pack_usage);\n\t\t}\n\t\tif (base_name)\n\t\t\tusage(pack_usage);\n\t\tbase_name = arg;\n\t}\n\n\tif (pack_to_stdout != !base_name)\n\t\tusage(pack_usage);\n\n\tprepare_packed_git();\n\n\tif (progress) {\n\t\tstruct itimerval v;\n\t\tv.it_interval.tv_sec = 1;\n\t\tv.it_interval.tv_usec = 0;\n\t\tv.it_value = v.it_interval;\n\t\tsignal(SIGALRM, progress_interval);\n\t\tsetitimer(ITIMER_REAL, &v, NULL);\n\t\tfprintf(stderr, \"Generating pack...\\n\");\n\t}\n\n\twhile (fgets(line, sizeof(line), stdin) != NULL) {\n\t\tunsigned char sha1[20];\n\n\t\tif (line[0] == '-') {\n\t\t\tif (get_sha1_hex(line+1, sha1))\n\t\t\t\tdie(\"expected edge sha1, got garbage:\\n %s\",\n\t\t\t\t line+1);\n\t\t\tadd_preferred_base(sha1);\n\t\t\tcontinue;\n\t\t}\n\t\tif (get_sha1_hex(line, sha1))\n\t\t\tdie(\"expected sha1, got garbage:\\n %s\", line);\n\t\tadd_object_entry(sha1, name_hash(NULL, line+41), 0);\n\t}\n\tif (progress)\n\t\tfprintf(stderr, \"Done counting %d objects.\\n\", nr_objects);\n\tsorted_by_sha = create_final_object_list();\n\tif (non_empty && !nr_result)\n\t\treturn 0;\n\n\tSHA1_Init(&ctx);\n\tlist = sorted_by_sha;\n\tfor (i = 0; i < nr_result; i++) {\n\t\tstruct object_entry *entry = *list++;\n\t\tSHA1_Update(&ctx, entry->sha1, 20);\n\t}\n\tSHA1_Final(object_list_sha1, &ctx);\n\tif (progress && (nr_objects != nr_result))\n\t\tfprintf(stderr, \"Result has %d objects.\\n\", nr_result);\n\n\tif (reuse_cached_pack(object_list_sha1, pack_to_stdout))\n\t\t;\n\telse {\n\t\tif (nr_result)\n\t\t\tprepare_pack(window, depth);\n\t\tif (progress && pack_to_stdout) {\n\t\t\t/* the other end usually displays progress itself */\n\t\t\tstruct itimerval v = {{0,},};\n\t\t\tsetitimer(ITIMER_REAL, &v, NULL);\n\t\t\tsignal(SIGALRM, SIG_IGN );\n\t\t\tprogress_update = 0;\n\t\t}\n\t\twrite_pack_file();\n\t\tif (!pack_to_stdout) {\n\t\t\twrite_index_file();\n\t\t\tputs(sha1_to_hex(object_list_sha1));\n\t\t}\n\t}\n\tif (progress)\n\t\tfprintf(stderr, \"Total %d, written %d (delta %d), reused %d (delta %d)\\n\",\n\t\t\tnr_result, written, written_delta, reused, reused_delta);\n\treturn 0;\n}\n"},{"id":"18298","messageId":"Pine.LNX.4.64.0604031222360.30048@alien.or.mcafeemobile.com","threadId":"3771","inReplyTo":"7v4q1bglkp.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-04-03T19:33:58Z","receivedAt":"2006-04-03T19:33:58Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Mon, 3 Apr 2006, Junio C Hamano wrote:\n\n> Davide Libenzi writes:\n>\n>> No problem. That's only an eye-issue though, since the diff is still a\n>> valid diff according to its definition where D=A-B => B+D==A && A-D==B\n>> From the day I released 0.18, xregression is continuosly running w/out\n>> any issue. I'll check it out though ...\n>\n> There is another to report, when ctxlen == 0.\n>\n> Between the attached files \"diff -u0 8f352aa dd40a03\", the\n> header for a hunk with only inserted lines misidentify the\n> original location.\n>\n> For example, the first hunk says:\n>\n> \t@@ -0,0 +6 @@\n> +#include \"diff.h\"\n>\n> Which is inconsistent with what GNU diff says:\n>\n> \t@@ -5,0 +6 @@\n> +#include \"diff.h\"\n>\n> I've tried this patch but it is not right; the diff between the\n> attached two files show a 47-line hunk that inserts at line 400,\n> then the next 6-line hunk inserts at line 401 which is obviously\n> bogus.\n>\n> diff --git a/xdiff/xutils.c b/xdiff/xutils.c\n> index afaada1..3e7f999 100644\n> --- a/xdiff/xutils.c\n> +++ b/xdiff/xutils.c\n> @@ -244,7 +244,7 @@ int xdl_emit_hunk_hdr(long s1, long c1,\n> \tmemcpy(buf, \"@@ -\", 4);\n> \tnb += 4;\n>\n> -\tnb += xdl_num_out(buf + nb, c1 ? s1: 0);\n> +\tnb += xdl_num_out(buf + nb, c1 ? s1 : (s1-1));\n>\n> \tif (c1 != 1) {\n> \t\tmemcpy(buf + nb, \",\", 1);\n\nThe fix is fine, but you should do the same even in the s2 case. The \ncorrect hunk should have been:\n\n@@ -6,0 +6 @@\n\nbecause the lines are actually inserted at the 6th position, but patch \nhandle its own special 0 count case by adding 1 to the position, so I had \nto change even the xpatchi.c code. The 0-context diffs are pretty \ndangerous though, since in case of purely added hunks, patch has no way to \nverify the orig-file position by matching contexts.\nNow I'll take a look at the pre-diff optimization issue ...\n\n\n\n- Davide\n\n\n\n--- xdiff/xpatchi.c\n+++ xdiff/xpatchi.c\n@@ -162,9 +162,9 @@\n \t * We start from zero, so decrement by one unless it's the special position\n \t * '0' inside the unified diff (new or deleted file).\n \t */\n-\tif (hki->s1 > 0)\n+\tif (hki->s1 > 0 && hki->c1 > 0)\n \t\thki->s1--;\n-\tif (hki->s2 > 0)\n+\tif (hki->s2 > 0 && hki->c2 > 0)\n \t\thki->s2--;\n\n \treturn 0;\n\n\n--- xdiff/xutils.c\n+++ xdiff/xutils.c\n@@ -537,7 +537,7 @@\n \tmemcpy(buf, \"@@ -\", 4);\n \tnb += 4;\n\n-\tnb += xdl_num_out(buf + nb, c1 ? s1: 0);\n+\tnb += xdl_num_out(buf + nb, c1 ? s1: s1 - 1);\n\n \tmemcpy(buf + nb, \",\", 1);\n \tnb += 1;\n@@ -547,7 +547,7 @@\n \tmemcpy(buf + nb, \" +\", 2);\n \tnb += 2;\n\n-\tnb += xdl_num_out(buf + nb, c2 ? s2: 0);\n+\tnb += xdl_num_out(buf + nb, c2 ? s2: s2 - 1);\n\n \tmemcpy(buf + nb, \",\", 1);\n \tnb += 1;\n"},{"id":"18300","messageId":"Pine.LNX.4.64.0604031240120.30048@alien.or.mcafeemobile.com","threadId":"3771","inReplyTo":"Pine.LNX.4.64.0604031222360.30048@alien.or.mcafeemobile.com","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-04-03T19:42:46Z","receivedAt":"2006-04-03T19:42:46Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Mon, 3 Apr 2006, Davide Libenzi wrote:\n\n> On Mon, 3 Apr 2006, Junio C Hamano wrote:\n>> \n>> I've tried this patch but it is not right; the diff between the\n>> attached two files show a 47-line hunk that inserts at line 400,\n>> then the next 6-line hunk inserts at line 401 which is obviously\n>> bogus.\n\nThat's fine, since that's orig file position *before* the insert. Try the \nsame with GNU diff and you should see the same. Also try to create a diff \nwith libxdiff (with the fix) and feed it to GNU patch.\n\n\n\n- Davide\n"},{"id":"18301","messageId":"7vbqvictsc.fsf@assigned-by-dhcp.cox.net","threadId":"3771","inReplyTo":"Pine.LNX.4.64.0604031222360.30048@alien.or.mcafeemobile.com","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-03T20:01:55Z","receivedAt":"2006-04-03T20:01:55Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Davide Libenzi writes:\n\n>> For example, the first hunk says:\n>>\n>> \t@@ -0,0 +6 @@\n>> +#include \"diff.h\"\n>>\n>> Which is inconsistent with what GNU diff says:\n>>\n>> \t@@ -5,0 +6 @@\n>> +#include \"diff.h\"\n>>\n>> I've tried this patch but...\n>\n> The fix is fine, but you should do the same even in the s2 case. The\n> correct hunk should have been:\n>\n> @@ -6,0 +6 @@\n\nYou are right. GNU says -5,0 not -6,0 so presumably \"patch\"\nother people use expect it to say -5,0 not -6,0; even though we\ncould argue the insertion happens at 6th position and saying\n-6,0 is more logical, it does not matter -- what incumbent does\nwins X-<. I notice that your fix shows -5,0 to match it ;-).\n\nThanks for the fix.\n"},{"id":"18311","messageId":"Pine.LNX.4.64.0604031548150.30048@alien.or.mcafeemobile.com","threadId":"3771","inReplyTo":"7vbqvictsc.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-04-03T22:50:42Z","receivedAt":"2006-04-03T22:50:42Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Mon, 3 Apr 2006, Junio C Hamano wrote:\n\n> Davide Libenzi writes:\n>\n>>> For example, the first hunk says:\n>>>\n>>> \t@@ -0,0 +6 @@\n>>> +#include \"diff.h\"\n>>>\n>>> Which is inconsistent with what GNU diff says:\n>>>\n>>> \t@@ -5,0 +6 @@\n>>> +#include \"diff.h\"\n>>>\n>>> I've tried this patch but...\n>>\n>> The fix is fine, but you should do the same even in the s2 case. The\n>> correct hunk should have been:\n>>\n>> @@ -6,0 +6 @@\n>\n> You are right. GNU says -5,0 not -6,0 so presumably \"patch\"\n> other people use expect it to say -5,0 not -6,0; even though we\n> could argue the insertion happens at 6th position and saying\n> -6,0 is more logical, it does not matter -- what incumbent does\n> wins X-<. I notice that your fix shows -5,0 to match it ;-).\n\nYeah, I had to make it such that GNU patch could swallow it, otherwise it \nmade no sense (being it right or not). Even the other issue is fixed now, \nand I'll send you a libxdiff-based diff as soon as it passes some tests.\n\n\n\n- Davide\n"},{"id":"18312","messageId":"Pine.LNX.4.64.0604031625330.30048@alien.or.mcafeemobile.com","threadId":"3771","inReplyTo":"7vzmj3k7x9.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-04-03T23:29:16Z","receivedAt":"2006-04-03T23:29:16Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Sun, 2 Apr 2006, Junio C Hamano wrote:\n\n> Davide Libenzi writes:\n>\n>> On Sun, 2 Apr 2006, Junio C Hamano wrote:\n>>\n>>> $ git diff-tree -p 52e8a6^2 52d8a6 -- git-fetch.sh\n>>>\n>>> shows a change that trivially is redundant, like this:\n>>>\n>>> diff --git a/git-fetch.sh b/git-fetch.sh\n>>> index b4325d9..de4f011 100755\n>>> --- a/git-fetch.sh\n>>> +++ b/git-fetch.sh\n>>> @@ -320,7 +320,7 @@ fetch_main () {\n>>> ..\n>>> Notice the first '-' and '+' lines of second hunk are identical?\n>>>\n>>> There is another interesting thing. This is running diff\n>>> between 52e8a6^2 and 52d8a6 blobs, but if I change them slightly\n>>> so that the first hunk is not different, then this anomaly\n>>> disappears.\n>>\n>> Could you send me the two files that creates the above diff?\n>\n> I should have tried your pristine xdiff code myself before\n> bothering you, but I haven't (sorry).\n>\n> The problem is from the \"stripped down\" version we use in git,\n> so you may or may not see the problem in your version. Attached\n> are the files.\n\nThis is the change I made to libxdiff. Xregression already made a few \nthousands on iterations w/out problems.\n\n\n\n- Davide\n\n\n\n--- xdiff/xdiffi.c\n+++ xdiff/xdiffi.c\n@@ -349,12 +349,7 @@\n \tkvdf += xe->xdf2.nreff + 1;\n \tkvdb += xe->xdf2.nreff + 1;\n\n-\t/*\n-\t * Classical integer square root approximation using shifts.\n-\t */\n-\txenv.mxcost = 1;\n-\tfor (; ndiags; ndiags >>= 2)\n-\t\txenv.mxcost <<= 1;\n+\txenv.mxcost = xdl_bogosqrt(ndiags);\n \tif (xenv.mxcost < XDL_MAX_COST_MIN)\n \t\txenv.mxcost = XDL_MAX_COST_MIN;\n \txenv.snake_cnt = XDL_SNAKE_CNT;\n\n\n--- xdiff/xprepare.c\n+++ xdiff/xprepare.c\n@@ -25,6 +25,7 @@\n\n\n #define XDL_KPDIS_RUN 4\n+#define XDL_MAX_EQLIMIT 1024\n\n\n\n@@ -305,26 +306,48 @@\n\n\n static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {\n-\tlong r, rdis, rpdis;\n+\tlong r, rdis0, rpdis0, rdis1, rpdis1;\n\n-\tfor (r = 1, rdis = 0, rpdis = 1; (i - r) >= s; r++) {\n+\t/*\n+\t * Scans the lines before 'i' to find a run of lines that either\n+\t * have no match (dis[j] == 0) or have multiple matches (dis[j] > 1).\n+\t * Note that we always call this function with dis[i] > 1, so the\n+\t * current line (i) is already a multimatch line.\n+\t */\n+\tfor (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) {\n \t\tif (!dis[i - r])\n-\t\t\trdis++;\n+\t\t\trdis0++;\n \t\telse if (dis[i - r] == 2)\n-\t\t\trpdis++;\n+\t\t\trpdis0++;\n \t\telse\n \t\t\tbreak;\n \t}\n-\tfor (r = 1; (i + r) <= e; r++) {\n+\t/*\n+\t * If the run before the line 'i' found only multimatch lines, we\n+\t * return 0 and hence we don't make the current line (i) discarded.\n+\t * We want to discard multimatch lines only when they appear in the\n+\t * middle of runs with nomatch lines (dis[j] == 0).\n+\t */\n+\tif (rdis0 == 0)\n+\t\treturn 0;\n+\tfor (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) {\n \t\tif (!dis[i + r])\n-\t\t\trdis++;\n+\t\t\trdis1++;\n \t\telse if (dis[i + r] == 2)\n-\t\t\trpdis++;\n+\t\t\trpdis1++;\n \t\telse\n \t\t\tbreak;\n \t}\n+\t/*\n+\t * If the run after the line 'i' found only multimatch lines, we\n+\t * return 0 and hence we don't make the current line (i) discarded.\n+\t */\n+\tif (rdis1 == 0)\n+\t\treturn 0;\n+\trdis1 += rdis0;\n+\trpdis1 += rpdis0;\n\n-\treturn rpdis * XDL_KPDIS_RUN < (rpdis + rdis);\n+\treturn rpdis1 * XDL_KPDIS_RUN < (rpdis1 + rdis1);\n }\n\n\n@@ -334,34 +357,40 @@\n * might be potentially discarded if they happear in a run of discardable.\n */\n static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {\n-\tlong i, rhi, nreff;\n+\tlong i, nm, rhi, nreff, mlim;\n \tunsigned long hav;\n \txrecord_t **recs;\n \txrecord_t *rec;\n \tchar *dis, *dis1, *dis2;\n\n-\tif (!(dis = (char *) xdl_malloc((xdf1->nrec + xdf2->nrec + 2) * sizeof(char)))) {\n+\tif (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) {\n\n \t\treturn -1;\n \t}\n-\tmemset(dis, 0, (xdf1->nrec + xdf2->nrec + 2) * sizeof(char));\n+\tmemset(dis, 0, xdf1->nrec + xdf2->nrec + 2);\n \tdis1 = dis;\n \tdis2 = dis1 + xdf1->nrec + 1;\n\n+\tif ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)\n+\t\tmlim = XDL_MAX_EQLIMIT;\n \tfor (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {\n \t\thav = (*recs)->ha;\n \t\trhi = (long) XDL_HASHLONG(hav, xdf2->hbits);\n-\t\tfor (rec = xdf2->rhash[rhi]; rec; rec = rec->next)\n-\t\t\tif (rec->ha == hav && ++dis1[i] == 2)\n+\t\tfor (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next)\n+\t\t\tif (rec->ha == hav && ++nm == mlim)\n \t\t\t\tbreak;\n+\t\tdis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n \t}\n\n+\tif ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)\n+\t\tmlim = XDL_MAX_EQLIMIT;\n \tfor (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {\n \t\thav = (*recs)->ha;\n \t\trhi = (long) XDL_HASHLONG(hav, xdf1->hbits);\n-\t\tfor (rec = xdf1->rhash[rhi]; rec; rec = rec->next)\n-\t\t\tif (rec->ha == hav && ++dis2[i] == 2)\n+\t\tfor (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next)\n+\t\t\tif (rec->ha == hav && ++nm == mlim)\n \t\t\t\tbreak;\n+\t\tdis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;\n \t}\n\n \tfor (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];\n\n\n--- xdiff/xutils.c\n+++ xdiff/xutils.c\n@@ -29,6 +29,19 @@\n\n\n\n+long xdl_bogosqrt(long n) {\n+\tlong i;\n+\n+\t/*\n+\t * Classical integer square root approximation using shifts.\n+\t */\n+\tfor (i = 1; n > 0; n >>= 2)\n+\t\ti <<= 1;\n+\n+\treturn i;\n+}\n+\n+\n int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,\n \t\t xdemitcb_t *ecb) {\n \tint i = 2;\n\n\n--- xdiff/xutils.h\n+++ xdiff/xutils.h\n@@ -25,6 +25,7 @@\n\n\n\n+long xdl_bogosqrt(long n);\n int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,\n \t\t xdemitcb_t *ecb);\n int xdl_mmfile_outf(void *priv, mmbuffer_t *mb, int nbuf);\n"},{"id":"18319","messageId":"7vslouayu8.fsf@assigned-by-dhcp.cox.net","threadId":"3771","inReplyTo":"Pine.LNX.4.64.0604031625330.30048@alien.or.mcafeemobile.com","subject":"Re: [RFH] xdiff shows trivially redundant diff.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-04T01:55:43Z","receivedAt":"2006-04-04T01:55:43Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Davide Libenzi writes:\n\n> This is the change I made to libxdiff. Xregression already made a few\n> thousands on iterations w/out problems.\n\nThanks. Merged-in and builds fine.\n"}]}