diff options
author | sra@chromium.org <sra@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98> | 2009-05-06 04:02:10 +0000 |
---|---|---|
committer | sra@chromium.org <sra@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98> | 2009-05-06 04:02:10 +0000 |
commit | f76b3b04a4c092d7db4cc2a75da4ca7fbac1f620 (patch) | |
tree | f32d9b1d982f427681c4c3a95c266afebf5e523a | |
parent | 5754c035975900ea5a48cb33aaa2c73d77c2cb35 (diff) | |
download | chromium_src-f76b3b04a4c092d7db4cc2a75da4ca7fbac1f620.zip chromium_src-f76b3b04a4c092d7db4cc2a75da4ca7fbac1f620.tar.gz chromium_src-f76b3b04a4c092d7db4cc2a75da4ca7fbac1f620.tar.bz2 |
Move Courgette from internal depot to third_party.
Review URL: http://codereview.chromium.org/113009
git-svn-id: svn://svn.chromium.org/chrome/trunk/src@15377 0039d316-1c4b-4281-b951-d872f2087c98
48 files changed, 8001 insertions, 0 deletions
diff --git a/build/all.gyp b/build/all.gyp index 1349cda..81526f5 100644 --- a/build/all.gyp +++ b/build/all.gyp @@ -57,6 +57,7 @@ ['OS=="win"', { 'dependencies': [ '../sandbox/sandbox.gyp:*', + '../third_party/courgette/courgette.gyp:*', '../webkit/activex_shim/activex_shim.gyp:*', '../webkit/activex_shim_dll/activex_shim_dll.gyp:*', 'temp_gyp/breakpad.gyp:*', diff --git a/chrome/chrome.sln b/chrome/chrome.sln index 6230912..9682814 100644 --- a/chrome/chrome.sln +++ b/chrome/chrome.sln @@ -720,6 +720,7 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "setup", "installer\setup\se {1832A374-8A74-4F9E-B536-69A699B3E165} = {1832A374-8A74-4F9E-B536-69A699B3E165} {899F1280-3441-4D1F-BA04-CCD6208D9146} = {899F1280-3441-4D1F-BA04-CCD6208D9146} {8C27D792-2648-4F5E-9ED0-374276327308} = {8C27D792-2648-4F5E-9ED0-374276327308} + {9A72A362-E617-4205-B9F2-43C6FB280FA1} = {9A72A362-E617-4205-B9F2-43C6FB280FA1} {B84553C8-5676-427B-B3E4-23DDDC4DBC7B} = {B84553C8-5676-427B-B3E4-23DDDC4DBC7B} {D7ED06E8-6138-4CE3-A906-5EF1D9C804E0} = {D7ED06E8-6138-4CE3-A906-5EF1D9C804E0} {EFBB1436-A63F-4CD8-9E99-B89226E782EC} = {EFBB1436-A63F-4CD8-9E99-B89226E782EC} @@ -749,6 +750,7 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "mini_installer", "installer {3AB90E6A-56FF-4C9D-B918-AB76DDBF8BE8} = {3AB90E6A-56FF-4C9D-B918-AB76DDBF8BE8} {3E6B24F6-9FA9-4066-859E-BF747FA3080A} = {3E6B24F6-9FA9-4066-859E-BF747FA3080A} {4B60E8B8-416F-40B2-8A54-F75970A21992} = {4B60E8B8-416F-40B2-8A54-F75970A21992} + {4EA8CE12-9C6F-45E5-9D08-720383FE3685} = {4EA8CE12-9C6F-45E5-9D08-720383FE3685} {5AEA4BF6-27CD-47FC-9370-D87771CFA196} = {5AEA4BF6-27CD-47FC-9370-D87771CFA196} {5BDB7EE1-A1FD-410C-9598-21519A1B7952} = {5BDB7EE1-A1FD-410C-9598-21519A1B7952} {63011A7B-CE4D-4DF1-B5DA-1B133C14A2E8} = {63011A7B-CE4D-4DF1-B5DA-1B133C14A2E8} @@ -1509,6 +1511,42 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "tcmalloc", "..\third_party\ EndProject Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "app", "..\app\app.vcproj", "{4631946D-7D5F-44BD-A5A8-504C0A7033BE}" EndProject +Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "courgette_lib", "..\third_party\courgette\courgette_lib.vcproj", "{9A72A362-E617-4205-B9F2-43C6FB280FA1}" +EndProject +Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "courgette_fuzz", "..\third_party\courgette\courgette_fuzz.vcproj", "{57C27529-8CA9-4FC3-9C02-DA05B172F785}" + ProjectSection(ProjectDependencies) = postProject + {1832A374-8A74-4F9E-B536-69A699B3E165} = {1832A374-8A74-4F9E-B536-69A699B3E165} + {8C27D792-2648-4F5E-9ED0-374276327308} = {8C27D792-2648-4F5E-9ED0-374276327308} + {9A72A362-E617-4205-B9F2-43C6FB280FA1} = {9A72A362-E617-4205-B9F2-43C6FB280FA1} + {BFE8E2A7-3B3B-43B0-A994-3058B852DB8B} = {BFE8E2A7-3B3B-43B0-A994-3058B852DB8B} + {F22022F0-2D3B-5610-4E80-C674A8E01C5A} = {F22022F0-2D3B-5610-4E80-C674A8E01C5A} + EndProjectSection +EndProject +Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "courgette_unittests", "..\third_party\courgette\courgette_unittests.vcproj", "{24309F1A-4035-46F9-A3D8-F47DC4BCC2B8}" + ProjectSection(ProjectDependencies) = postProject + {1832A374-8A74-4F9E-B536-69A699B3E165} = {1832A374-8A74-4F9E-B536-69A699B3E165} + {8C27D792-2648-4F5E-9ED0-374276327308} = {8C27D792-2648-4F5E-9ED0-374276327308} + {9A72A362-E617-4205-B9F2-43C6FB280FA1} = {9A72A362-E617-4205-B9F2-43C6FB280FA1} + {BFE8E2A7-3B3B-43B0-A994-3058B852DB8B} = {BFE8E2A7-3B3B-43B0-A994-3058B852DB8B} + {F22022F0-2D3B-5610-4E80-C674A8E01C5A} = {F22022F0-2D3B-5610-4E80-C674A8E01C5A} + EndProjectSection +EndProject +Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "courgette_tool", "..\third_party\courgette\courgette_tool.vcproj", "{4EA8CE12-9C6F-45E5-9D08-720383FE3685}" + ProjectSection(ProjectDependencies) = postProject + {1832A374-8A74-4F9E-B536-69A699B3E165} = {1832A374-8A74-4F9E-B536-69A699B3E165} + {8C27D792-2648-4F5E-9ED0-374276327308} = {8C27D792-2648-4F5E-9ED0-374276327308} + {9A72A362-E617-4205-B9F2-43C6FB280FA1} = {9A72A362-E617-4205-B9F2-43C6FB280FA1} + {F22022F0-2D3B-5610-4E80-C674A8E01C5A} = {F22022F0-2D3B-5610-4E80-C674A8E01C5A} + EndProjectSection +EndProject +Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "courgette_minimal_tool", "..\third_party\courgette\courgette_minimal_tool.vcproj", "{EB79415F-2F17-4BDC-AADD-4CA4C2D21B73}" + ProjectSection(ProjectDependencies) = postProject + {1832A374-8A74-4F9E-B536-69A699B3E165} = {1832A374-8A74-4F9E-B536-69A699B3E165} + {8C27D792-2648-4F5E-9ED0-374276327308} = {8C27D792-2648-4F5E-9ED0-374276327308} + {9A72A362-E617-4205-B9F2-43C6FB280FA1} = {9A72A362-E617-4205-B9F2-43C6FB280FA1} + {F22022F0-2D3B-5610-4E80-C674A8E01C5A} = {F22022F0-2D3B-5610-4E80-C674A8E01C5A} + EndProjectSection +EndProject Global GlobalSection(SolutionConfigurationPlatforms) = preSolution Debug|Mixed Platforms = Debug|Mixed Platforms @@ -1668,6 +1706,14 @@ Global {238CE175-76CE-4A25-A676-69D115885601}.Release|Mixed Platforms.Build.0 = Release|Win32 {238CE175-76CE-4A25-A676-69D115885601}.Release|Win32.ActiveCfg = Release|Win32 {238CE175-76CE-4A25-A676-69D115885601}.Release|Win32.Build.0 = Release|Win32 + {24309F1A-4035-46F9-A3D8-F47DC4BCC2B8}.Debug|Mixed Platforms.ActiveCfg = Debug|Win32 + {24309F1A-4035-46F9-A3D8-F47DC4BCC2B8}.Debug|Mixed Platforms.Build.0 = Debug|Win32 + {24309F1A-4035-46F9-A3D8-F47DC4BCC2B8}.Debug|Win32.ActiveCfg = Debug|Win32 + {24309F1A-4035-46F9-A3D8-F47DC4BCC2B8}.Debug|Win32.Build.0 = Debug|Win32 + {24309F1A-4035-46F9-A3D8-F47DC4BCC2B8}.Release|Mixed Platforms.ActiveCfg = Release|Win32 + {24309F1A-4035-46F9-A3D8-F47DC4BCC2B8}.Release|Mixed Platforms.Build.0 = Release|Win32 + {24309F1A-4035-46F9-A3D8-F47DC4BCC2B8}.Release|Win32.ActiveCfg = Release|Win32 + {24309F1A-4035-46F9-A3D8-F47DC4BCC2B8}.Release|Win32.Build.0 = Release|Win32 {24A5AC7C-280B-4899-9153-6BA570A081E7}.Debug|Mixed Platforms.ActiveCfg = Debug|Win32 {24A5AC7C-280B-4899-9153-6BA570A081E7}.Debug|Win32.ActiveCfg = Debug|Win32 {24A5AC7C-280B-4899-9153-6BA570A081E7}.Release|Mixed Platforms.ActiveCfg = Release|Win32 @@ -1885,6 +1931,14 @@ Global {4B6E199A-034A-49BD-AB93-458DD37E45B1}.Release|Mixed Platforms.Build.0 = Release|Win32 {4B6E199A-034A-49BD-AB93-458DD37E45B1}.Release|Win32.ActiveCfg = Release|Win32 {4B6E199A-034A-49BD-AB93-458DD37E45B1}.Release|Win32.Build.0 = Release|Win32 + {4EA8CE12-9C6F-45E5-9D08-720383FE3685}.Debug|Mixed Platforms.ActiveCfg = Debug|Win32 + {4EA8CE12-9C6F-45E5-9D08-720383FE3685}.Debug|Mixed Platforms.Build.0 = Debug|Win32 + {4EA8CE12-9C6F-45E5-9D08-720383FE3685}.Debug|Win32.ActiveCfg = Debug|Win32 + {4EA8CE12-9C6F-45E5-9D08-720383FE3685}.Debug|Win32.Build.0 = Debug|Win32 + {4EA8CE12-9C6F-45E5-9D08-720383FE3685}.Release|Mixed Platforms.ActiveCfg = Release|Win32 + {4EA8CE12-9C6F-45E5-9D08-720383FE3685}.Release|Mixed Platforms.Build.0 = Release|Win32 + {4EA8CE12-9C6F-45E5-9D08-720383FE3685}.Release|Win32.ActiveCfg = Release|Win32 + {4EA8CE12-9C6F-45E5-9D08-720383FE3685}.Release|Win32.Build.0 = Release|Win32 {50B079C7-CD01-42D3-B8C4-9F8D9322E822}.Debug|Mixed Platforms.ActiveCfg = Debug|Win32 {50B079C7-CD01-42D3-B8C4-9F8D9322E822}.Debug|Mixed Platforms.Build.0 = Debug|Win32 {50B079C7-CD01-42D3-B8C4-9F8D9322E822}.Debug|Win32.ActiveCfg = Debug|Win32 @@ -1909,6 +1963,14 @@ Global {57823D8C-A317-4713-9125-2C91FDFD12D6}.Release|Mixed Platforms.Build.0 = Release|Win32 {57823D8C-A317-4713-9125-2C91FDFD12D6}.Release|Win32.ActiveCfg = Release|Win32 {57823D8C-A317-4713-9125-2C91FDFD12D6}.Release|Win32.Build.0 = Release|Win32 + {57C27529-8CA9-4FC3-9C02-DA05B172F785}.Debug|Mixed Platforms.ActiveCfg = Debug|Win32 + {57C27529-8CA9-4FC3-9C02-DA05B172F785}.Debug|Mixed Platforms.Build.0 = Debug|Win32 + {57C27529-8CA9-4FC3-9C02-DA05B172F785}.Debug|Win32.ActiveCfg = Debug|Win32 + {57C27529-8CA9-4FC3-9C02-DA05B172F785}.Debug|Win32.Build.0 = Debug|Win32 + {57C27529-8CA9-4FC3-9C02-DA05B172F785}.Release|Mixed Platforms.ActiveCfg = Release|Win32 + {57C27529-8CA9-4FC3-9C02-DA05B172F785}.Release|Mixed Platforms.Build.0 = Release|Win32 + {57C27529-8CA9-4FC3-9C02-DA05B172F785}.Release|Win32.ActiveCfg = Release|Win32 + {57C27529-8CA9-4FC3-9C02-DA05B172F785}.Release|Win32.Build.0 = Release|Win32 {5916D37D-8C97-424F-A904-74E52594C2D6}.Debug|Mixed Platforms.ActiveCfg = Debug|Win32 {5916D37D-8C97-424F-A904-74E52594C2D6}.Debug|Mixed Platforms.Build.0 = Debug|Win32 {5916D37D-8C97-424F-A904-74E52594C2D6}.Debug|Win32.ActiveCfg = Debug|Win32 @@ -2221,6 +2283,14 @@ Global {9946A048-043B-4F8F-9E07-9297B204714C}.Release|Mixed Platforms.Build.0 = Release|Win32 {9946A048-043B-4F8F-9E07-9297B204714C}.Release|Win32.ActiveCfg = Release|Win32 {9946A048-043B-4F8F-9E07-9297B204714C}.Release|Win32.Build.0 = Release|Win32 + {9A72A362-E617-4205-B9F2-43C6FB280FA1}.Debug|Mixed Platforms.ActiveCfg = Debug|Win32 + {9A72A362-E617-4205-B9F2-43C6FB280FA1}.Debug|Mixed Platforms.Build.0 = Debug|Win32 + {9A72A362-E617-4205-B9F2-43C6FB280FA1}.Debug|Win32.ActiveCfg = Debug|Win32 + {9A72A362-E617-4205-B9F2-43C6FB280FA1}.Debug|Win32.Build.0 = Debug|Win32 + {9A72A362-E617-4205-B9F2-43C6FB280FA1}.Release|Mixed Platforms.ActiveCfg = Release|Win32 + {9A72A362-E617-4205-B9F2-43C6FB280FA1}.Release|Mixed Platforms.Build.0 = Release|Win32 + {9A72A362-E617-4205-B9F2-43C6FB280FA1}.Release|Win32.ActiveCfg = Release|Win32 + {9A72A362-E617-4205-B9F2-43C6FB280FA1}.Release|Win32.Build.0 = Release|Win32 {9B87804D-2502-480B-95AE-5A572CE91809}.Debug|Mixed Platforms.ActiveCfg = Debug|Win32 {9B87804D-2502-480B-95AE-5A572CE91809}.Debug|Mixed Platforms.Build.0 = Debug|Win32 {9B87804D-2502-480B-95AE-5A572CE91809}.Debug|Win32.ActiveCfg = Debug|Win32 @@ -2743,6 +2813,14 @@ Global {E99DA267-BE90-4F45-88A1-6919DB2C7567}.Release|Mixed Platforms.ActiveCfg = Release|Win32 {E99DA267-BE90-4F45-88A1-6919DB2C7567}.Release|Mixed Platforms.Build.0 = Release|Win32 {E99DA267-BE90-4F45-88A1-6919DB2C7567}.Release|Win32.ActiveCfg = Release|Win32 + {EB79415F-2F17-4BDC-AADD-4CA4C2D21B73}.Debug|Mixed Platforms.ActiveCfg = Debug|Win32 + {EB79415F-2F17-4BDC-AADD-4CA4C2D21B73}.Debug|Mixed Platforms.Build.0 = Debug|Win32 + {EB79415F-2F17-4BDC-AADD-4CA4C2D21B73}.Debug|Win32.ActiveCfg = Debug|Win32 + {EB79415F-2F17-4BDC-AADD-4CA4C2D21B73}.Debug|Win32.Build.0 = Debug|Win32 + {EB79415F-2F17-4BDC-AADD-4CA4C2D21B73}.Release|Mixed Platforms.ActiveCfg = Release|Win32 + {EB79415F-2F17-4BDC-AADD-4CA4C2D21B73}.Release|Mixed Platforms.Build.0 = Release|Win32 + {EB79415F-2F17-4BDC-AADD-4CA4C2D21B73}.Release|Win32.ActiveCfg = Release|Win32 + {EB79415F-2F17-4BDC-AADD-4CA4C2D21B73}.Release|Win32.Build.0 = Release|Win32 {EC8B7909-62AF-470D-A75D-E1D89C837142}.Debug|Mixed Platforms.ActiveCfg = Debug|Win32 {EC8B7909-62AF-470D-A75D-E1D89C837142}.Debug|Mixed Platforms.Build.0 = Debug|Win32 {EC8B7909-62AF-470D-A75D-E1D89C837142}.Debug|Win32.ActiveCfg = Debug|Win32 @@ -2888,6 +2966,7 @@ Global {228DD844-9926-420E-B193-6973BF2A4D0B} = {2325D8C4-8EF5-42AC-8900-492225750DE4} {2325D8C4-8EF5-42AC-8900-492225750DE4} = {B6867423-23BD-4588-9321-2D500F128A3D} {238CE175-76CE-4A25-A676-69D115885601} = {EF78C1F9-AA17-4CA5-B6CB-39B37A73A3DA} + {24309F1A-4035-46F9-A3D8-F47DC4BCC2B8} = {1174D37F-6ABB-45DA-81B3-C631281273B7} {24A5AC7C-280B-4899-9153-6BA570A081E7} = {EB684A4B-98F7-4E68-8EA7-EA74ACF7060B} {256DECCE-9886-4C21-96A5-EE47DF5E07E9} = {2325D8C4-8EF5-42AC-8900-492225750DE4} {275F2993-EE9B-4E00-9C85-10A182FD423A} = {2325D8C4-8EF5-42AC-8900-492225750DE4} @@ -2915,9 +2994,11 @@ Global {49909552-0B0C-4C14-8CF6-DB8A2ADE0934} = {1088577A-0C49-4DE0-85CD-B68AD0BE55AA} {4B60E8B8-416F-40B2-8A54-F75970A21992} = {2325D8C4-8EF5-42AC-8900-492225750DE4} {4B6E199A-034A-49BD-AB93-458DD37E45B1} = {1174D37F-6ABB-45DA-81B3-C631281273B7} + {4EA8CE12-9C6F-45E5-9D08-720383FE3685} = {846901FD-A619-4BD5-A303-38174730CDD6} {50B079C7-CD01-42D3-B8C4-9F8D9322E822} = {1174D37F-6ABB-45DA-81B3-C631281273B7} {5597AD47-3494-4750-A235-4F9C2F864700} = {CB43561E-A6F8-49E2-96A2-3F2BA1FFF21E} {57823D8C-A317-4713-9125-2C91FDFD12D6} = {97555540-8163-4D0F-BCAC-EFA0FFED3453} + {57C27529-8CA9-4FC3-9C02-DA05B172F785} = {1174D37F-6ABB-45DA-81B3-C631281273B7} {5916D37D-8C97-424F-A904-74E52594C2D6} = {CB43561E-A6F8-49E2-96A2-3F2BA1FFF21E} {5AEA4BF6-27CD-47FC-9370-D87771CFA196} = {2325D8C4-8EF5-42AC-8900-492225750DE4} {5BDB7EE1-A1FD-410C-9598-21519A1B7952} = {2325D8C4-8EF5-42AC-8900-492225750DE4} @@ -2958,6 +3039,7 @@ Global {9055E088-25C6-47FD-87D5-D9DD9FD75C9F} = {1174D37F-6ABB-45DA-81B3-C631281273B7} {9301A569-5D2B-4D11-9332-B1E30AEACB8D} = {97555540-8163-4D0F-BCAC-EFA0FFED3453} {9946A048-043B-4F8F-9E07-9297B204714C} = {873D095E-150E-4262-8C41-2D8ED02F0F57} + {9A72A362-E617-4205-B9F2-43C6FB280FA1} = {EF78C1F9-AA17-4CA5-B6CB-39B37A73A3DA} {9B87804D-2502-480B-95AE-5A572CE91809} = {1174D37F-6ABB-45DA-81B3-C631281273B7} {9D13D9B8-6C28-42A7-935C-B769EBC55BAA} = {2325D8C4-8EF5-42AC-8900-492225750DE4} {9E5416B9-B91B-4029-93F4-102C1AD5CAF4} = {EF78C1F9-AA17-4CA5-B6CB-39B37A73A3DA} @@ -3025,6 +3107,7 @@ Global {E750512D-FC7C-4C98-BF04-0A0DAF882055} = {1174D37F-6ABB-45DA-81B3-C631281273B7} {E7B11CF0-FE40-4A69-AE20-1B882F4D7585} = {2325D8C4-8EF5-42AC-8900-492225750DE4} {E99DA267-BE90-4F45-88A1-6919DB2C7567} = {1174D37F-6ABB-45DA-81B3-C631281273B7} + {EB79415F-2F17-4BDC-AADD-4CA4C2D21B73} = {846901FD-A619-4BD5-A303-38174730CDD6} {EC8B7909-62AF-470D-A75D-E1D89C837142} = {B353A6A5-9551-4B76-908E-0F0A9B31E4CE} {ECFC2BEC-9FC0-4AD9-9649-5F26793F65FC} = {1174D37F-6ABB-45DA-81B3-C631281273B7} {ED19720A-8F14-D3FC-9C6D-EEB5AE4D5BD7} = {EF78C1F9-AA17-4CA5-B6CB-39B37A73A3DA} diff --git a/third_party/courgette/LICENCE.bsdiff b/third_party/courgette/LICENCE.bsdiff new file mode 100644 index 0000000..c146b5b --- /dev/null +++ b/third_party/courgette/LICENCE.bsdiff @@ -0,0 +1,121 @@ +BSD Protection License +February 2002 + +Preamble +-------- + +The Berkeley Software Distribution ("BSD") license has proven very effective +over the years at allowing for a wide spread of work throughout both +commercial and non-commercial products. For programmers whose primary +intention is to improve the general quality of available software, it is +arguable that there is no better license than the BSD license, as it +permits improvements to be used wherever they will help, without idealogical +or metallic constraint. + +This is of particular value to those who produce reference implementations +of proposed standards: The case of TCP/IP clearly illustrates that freely +and universally available implementations leads the rapid acceptance of +standards -- often even being used instead of a de jure standard (eg, OSI +network models). + +With the rapid proliferation of software licensed under the GNU General +Public License, however, the continued success of this role is called into +question. Given that the inclusion of a few lines of "GPL-tainted" work +into a larger body of work will result in restricted distribution -- and +given that further work will likely build upon the "tainted" portions, +making them difficult to remove at a future date -- there are inevitable +circumstances where authors would, in order to protect their goal of +providing for the widespread usage of their work, wish to guard against +such "GPL-taint". + +In addition, one can imagine that companies which operate by producing and +selling (possibly closed-source) code would wish to protect themselves +against the rise of a GPL-licensed competitor. While under existing +licenses this would mean not releasing their code under any form of open +license, if a license existed under which they could incorporate any +improvements back into their own (commercial) products then they might be +far more willing to provide for non-closed distribution. + +For the above reasons, we put forth this "BSD Protection License": A +license designed to retain the freedom granted by the BSD license to use +licensed works in a wide variety of settings, both non-commercial and +commercial, while protecting the work from having future contributors +restrict that freedom. + +The precise terms and conditions for copying, distribution, and +modification follow. + +BSD PROTECTION LICENSE +TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION, AND MODIFICATION +---------------------------------------------------------------- + +0. Definitions. + a) "Program", below, refers to any program or work distributed under + the terms of this license. + b) A "work based on the Program", below, refers to either the Program + or any derivative work under copyright law. + c) "Modification", below, refers to the act of creating derivative works. + d) "You", below, refers to each licensee. + +1. Scope. + This license governs the copying, distribution, and modification of the + Program. Other activities are outside the scope of this license; The + act of running the Program is not restricted, and the output from the + Program is covered only if its contents constitute a work based on the + Program. + +2. Verbatim copies. + You may copy and distribute verbatim copies of the Program as you + receive it, in any medium, provided that you conspicuously and + appropriately publish on each copy an appropriate copyright notice; keep + intact all the notices that refer to this License and to the absence of + any warranty; and give any other recipients of the Program a copy of this + License along with the Program. + +3. Modification and redistribution under closed license. + You may modify your copy or copies of the Program, and distribute + the resulting derivative works, provided that you meet the + following conditions: + a) The copyright notice and disclaimer on the Program must be reproduced + and included in the source code, documentation, and/or other materials + provided in a manner in which such notices are normally distributed. + b) The derivative work must be clearly identified as such, in order that + it may not be confused with the original work. + c) The license under which the derivative work is distributed must + expressly prohibit the distribution of further derivative works. + +4. Modification and redistribution under open license. + You may modify your copy or copies of the Program, and distribute + the resulting derivative works, provided that you meet the + following conditions: + a) The copyright notice and disclaimer on the Program must be reproduced + and included in the source code, documentation, and/or other materials + provided in a manner in which such notices are normally distributed. + b) You must clearly indicate the nature and date of any changes made + to the Program. The full details need not necessarily be included in + the individual modified files, provided that each modified file is + clearly marked as such and instructions are included on where the + full details of the modifications may be found. + c) You must cause any work that you distribute or publish, that in whole + or in part contains or is derived from the Program or any part + thereof, to be licensed as a whole at no charge to all third + parties under the terms of this License. + +5. Implied acceptance. + You may not copy or distribute the Program or any derivative works except + as expressly provided under this license. Consequently, any such action + will be taken as implied acceptance of the terms of this license. + +6. NO WARRANTY. + THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY + AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL + THE COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR + REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE FOR ANY DIRECT, + INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING, BUT + NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF + USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR + TORT, EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE + POSSIBILITY OF SUCH DAMAGES. diff --git a/third_party/courgette/adjustment_method.cc b/third_party/courgette/adjustment_method.cc new file mode 100644 index 0000000..8f6caef --- /dev/null +++ b/third_party/courgette/adjustment_method.cc @@ -0,0 +1,703 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "third_party/courgette/adjustment_method.h"
+
+#include <algorithm>
+#include <list>
+#include <map>
+#include <set>
+#include <string>
+#include <vector>
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+#include "base/string_util.h"
+
+#include "third_party/courgette/assembly_program.h"
+#include "third_party/courgette/courgette.h"
+#include "third_party/courgette/encoded_program.h"
+#include "third_party/courgette/image_info.h"
+
+namespace courgette {
+
+// We have three discretionary information logging levels for algorithm
+// development. For now just configure with #defines.
+// TODO(sra): make dependent of some configurable setting.
+#define NO_LOG DLOG_IF(INFO, false)
+// #define ALOG1 LOG(INFO)
+// #define ALOG2 LOG(INFO)
+// #define ALOG3 LOG(INFO)
+#define ALOG1 NO_LOG
+#define ALOG2 NO_LOG
+#define ALOG3 NO_LOG
+
+////////////////////////////////////////////////////////////////////////////////
+
+class NullAdjustmentMethod : public AdjustmentMethod {
+ bool Adjust(const AssemblyProgram& model, AssemblyProgram* program) {
+ return true;
+ }
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+// The purpose of adjustment is to assign indexes to Labels of a program 'p' to
+// make the sequence of indexes similar to a 'model' program 'm'. Labels
+// themselves don't have enough information to do this job, so we work with a
+// LabelInfo surrogate for each label.
+//
+class LabelInfo {
+ public:
+ Label* label_; // The label that this info a surrogate for.
+
+ // Information used only in debugging messages.
+ uint32 is_model_ : 1; // Is the label in the model?
+ uint32 debug_index_ : 31; // An unique small number for naming the label.
+
+ uint32 refs_; // Number of times this Label is referenced.
+
+ LabelInfo* assignment_; // Label from other program corresponding to this.
+
+ // LabelInfos are in a doubly linked list ordered by address (label_->rva_) so
+ // we can quickly find Labels adjacent in address order.
+ LabelInfo* next_addr_; // Label(Info) at next highest address.
+ LabelInfo* prev_addr_; // Label(Info) at next lowest address.
+
+ std::vector<uint32> positions_; // Offsets into the trace of references.
+
+ // Just a no-argument constructor and copy constructor. Actual LabelInfo
+ // objects are allocated in std::pair structs in a std::map.
+ LabelInfo()
+ : label_(NULL), is_model_(false), debug_index_(0), refs_(0),
+ assignment_(NULL),
+ next_addr_(NULL),
+ prev_addr_(NULL) {}
+
+ private:
+ void operator=(const LabelInfo*); // Disallow assignment only.
+
+ // Public compiler generated copy constructor is needed to constuct
+ // std::pair<Label*, LabelInfo> so that fresh LabelInfos can be allocated
+ // inside a std::map.
+};
+
+struct OrderLabelInfoByAddressAscending {
+ bool operator()(const LabelInfo* a, const LabelInfo* b) const {
+ return a->label_->rva_ < b->label_->rva_;
+ }
+};
+
+static std::string ToString(LabelInfo* info) {
+ std::string s;
+ StringAppendF(&s, "%c%d", "pm"[info->is_model_], info->debug_index_);
+ if (info->label_->index_ != Label::kNoIndex)
+ StringAppendF(&s, " (%d)", info->label_->index_);
+
+ StringAppendF(&s, " #%u", info->refs_);
+ return s;
+}
+
+// General graph matching is exponential, essentially trying all permutations.
+// The exponential algorithm can be made faster by avoiding consideration of
+// impossible or unlikely matches. We can make the matching practical by eager
+// matching - by looking for likely matches and commiting to them, and using the
+// committed assignment as the basis for further matching.
+//
+// The basic eager graph-matching assignment is based on several ideas:
+//
+// * The strongest match will be for parts of the program that have not
+// changed. If part of a program has not changed, then the number of
+// references to a label will be the same, and corresponding pairs of
+// adjacent labels will have the same RVA difference.
+//
+// * Some assignments are 'obvious' if you look at the distribution. Example:
+// if both the program and the model have a label that is referred to much
+// more often than the next most refered-to label, it is likely the two
+// labels correspond.
+//
+// * If a label from the program corresponds to a label in the model, it is
+// likely that the labels near the corresponding labels also match. A
+// conservative way of extending the match is to assign only those labels
+// which have exactly the same address offset and reference count.
+//
+// * If two labels correspond, then we can try to match up the references
+// before and after the labels in the reference stream. For this to be
+// practical, the number of references has to be small, e.g. each label has
+// exactly one reference.
+//
+
+// Note: we also tried a completely different approach: random assignment
+// followed by simulated annealing. This produced similar results. The results
+// were not as good for very small differences because the simulated annealing
+// never quite hit the groove. And simulated annealing was several orders of
+// magnitude slower.
+
+
+// TRIE node for suffix strings in the label reference sequence.
+//
+// We dynamically build a trie for both the program and model, growing the trie
+// as necessary. The trie node for a (possibly) empty string of label
+// references contains the distribution of labels following the string. The
+// roots node (for the empty string) thus contains the simple distribution of
+// labels within the label reference stream.
+
+struct Node {
+ Node(LabelInfo* in_edge, Node* prev)
+ : in_edge_(in_edge), prev_(prev), count_(0),
+ in_queue_(false) {
+ length_ = 1 + (prev_ ? prev_->length_ : 0);
+ }
+ LabelInfo* in_edge_; //
+ Node* prev_; // Node at shorter length.
+ int count_; // Frequency of this path in Trie.
+ int length_;
+ typedef std::map<LabelInfo*, Node*> Edges;
+ Edges edges_;
+ std::vector<int> places_; // Indexes into sequence of this item.
+ std::list<Node*> edges_in_frequency_order;
+
+ bool in_queue_;
+ bool Extended() const { return edges_.size() > 0; }
+
+ uint32 Weight() const {
+ return edges_in_frequency_order.front()->count_;
+ }
+};
+
+static std::string ToString(Node* node) {
+ std::vector<std::string> prefix;
+ for (Node* n = node; n->prev_; n = n->prev_)
+ prefix.push_back(ToString(n->in_edge_));
+
+ std::string s;
+ s += "{";
+ const char* sep = "";
+ while (!prefix.empty()) {
+ s += sep;
+ sep = ",";
+ s += prefix.back();
+ prefix.pop_back();
+ }
+
+ s += StringPrintf("%u", node->count_);
+ s += " @";
+ s += Uint64ToString(node->edges_in_frequency_order.size());
+ s += "}";
+ return s;
+}
+
+typedef std::vector<LabelInfo*> Trace;
+
+struct OrderNodeByCountDecreasing {
+ bool operator()(Node* a, Node* b) const {
+ if (a->count_ != b->count_)
+ return (a->count_) > (b->count_);
+ return a->places_.at(0) < b->places_.at(0); // Prefer first occuring.
+ }
+};
+
+struct OrderNodeByWeightDecreasing {
+ bool operator()(Node* a, Node* b) const {
+ // (Maybe tie-break on total count, followed by lowest assigned node indexes
+ // in path.)
+ uint32 a_weight = a->Weight();
+ uint32 b_weight = b->Weight();
+ if (a_weight != b_weight)
+ return a_weight > b_weight;
+ if (a->length_ != b->length_)
+ return a->length_ > b->length_; // Prefer longer.
+ return a->places_.at(0) < b->places_.at(0); // Prefer first occuring.
+ }
+};
+
+typedef std::set<Node*, OrderNodeByWeightDecreasing> NodeQueue;
+
+class AssignmentProblem {
+ public:
+ AssignmentProblem(const Trace& model,
+ const Trace& problem)
+ : m_trace_(model),
+ p_trace_(problem) {
+ }
+
+ ~AssignmentProblem() {
+ for (size_t i = 0; i < all_nodes_.size(); ++i)
+ delete all_nodes_[i];
+ }
+
+ bool Solve() {
+ m_root_ = MakeRootNode(m_trace_);
+ p_root_ = MakeRootNode(p_trace_);
+ AddToQueue(p_root_);
+
+ while (!worklist_.empty()) {
+ Node* node = *worklist_.begin();
+ node->in_queue_ = false;
+ worklist_.erase(node);
+ TrySolveNode(node);
+ }
+
+ ALOG1 << unsolved_.size() << " unsolved items";
+ return true;
+ }
+
+ private:
+ void AddToQueue(Node* node) {
+ if (node->length_ >= 10) {
+ ALOG3 << "Length clipped " << ToString(node->prev_);
+ return;
+ }
+ if (node->in_queue_) {
+ LOG(ERROR) << "Double add " << ToString(node);
+ return;
+ }
+ // just to be sure data for prioritizing is available
+ ExtendNode(node, p_trace_);
+ // SkipCommittedLabels(node);
+ if (node->edges_in_frequency_order.empty())
+ return;
+ node->in_queue_ = true;
+ worklist_.insert(node);
+ }
+
+ void SkipCommittedLabels(Node* node) {
+ ExtendNode(node, p_trace_);
+ uint32 skipped = 0;
+ while (!node->edges_in_frequency_order.empty() &&
+ node->edges_in_frequency_order.front()->in_edge_->assignment_) {
+ ++skipped;
+ node->edges_in_frequency_order.pop_front();
+ }
+ if (skipped > 0)
+ ALOG3 << "Skipped " << skipped << " at " << ToString(node);
+ }
+
+ void TrySolveNode(Node* p_node) {
+ Node* front = p_node->edges_in_frequency_order.front();
+ if (front->in_edge_->assignment_) {
+ p_node->edges_in_frequency_order.pop_front();
+ AddToQueue(front);
+ AddToQueue(p_node);
+ return;
+ }
+
+ // Compare frequencies of unassigned edges, and either make
+ // assignment(s) or move node to unsolved list
+
+ Node* m_node = FindModelNode(p_node);
+
+ if (m_node == NULL) {
+ ALOG1 << "Can't find model node";
+ unsolved_.insert(p_node);
+ return;
+ }
+ ExtendNode(m_node, m_trace_);
+
+ // Lets just try greedy
+
+ SkipCommittedLabels(m_node);
+ if (m_node->edges_in_frequency_order.empty()) {
+ ALOG3 << "Punting, no elements left in model vs "
+ << p_node->edges_in_frequency_order.size();
+ unsolved_.insert(p_node);
+ return;
+ }
+ Node* m_match = m_node->edges_in_frequency_order.front();
+ Node* p_match = p_node->edges_in_frequency_order.front();
+
+ if (p_match->count_ > 1.1 * m_match->count_ ||
+ m_match->count_ > 1.1 * p_match->count_) {
+ ALOG2 << "Tricky distribution "
+ << p_match->count_ << ":" << m_match->count_ << " "
+ << ToString(p_match) << " vs " << ToString(m_match);
+ return;
+ }
+
+ m_node->edges_in_frequency_order.pop_front();
+ p_node->edges_in_frequency_order.pop_front();
+
+ LabelInfo* p_label_info = p_match->in_edge_;
+ LabelInfo* m_label_info = m_match->in_edge_;
+ int m_index = p_label_info->label_->index_;
+ if (m_index != Label::kNoIndex) {
+ ALOG1 << "Cant use unassigned label from model " << m_index;
+ unsolved_.insert(p_node);
+ return;
+ }
+
+ Assign(p_label_info, m_label_info);
+
+ AddToQueue(p_match); // find matches within new match
+ AddToQueue(p_node); // and more matches within this node
+ }
+
+ void Assign(LabelInfo* p_info, LabelInfo* m_info) {
+ AssignOne(p_info, m_info);
+ ALOG3 << "Assign " << ToString(p_info) << " := " << ToString(m_info);
+ // Now consider unassigned adjacent addresses
+ TryExtendAssignment(p_info, m_info);
+ }
+
+ void AssignOne(LabelInfo* p_info, LabelInfo* m_info) {
+ p_info->label_->index_ = m_info->label_->index_;
+
+ // Mark as assigned
+ m_info->assignment_ = p_info;
+ p_info->assignment_ = m_info;
+ }
+
+ void TryExtendAssignment(LabelInfo* p_info, LabelInfo* m_info) {
+ RVA m_rva_base = m_info->label_->rva_;
+ RVA p_rva_base = p_info->label_->rva_;
+
+ LabelInfo* m_info_next = m_info->next_addr_;
+ LabelInfo* p_info_next = p_info->next_addr_;
+ for ( ; m_info_next && p_info_next; ) {
+ if (m_info_next->assignment_)
+ break;
+
+ RVA m_rva = m_info_next->label_->rva_;
+ RVA p_rva = p_info_next->label_->rva_;
+
+ if (m_rva - m_rva_base != p_rva - p_rva_base) {
+ // previous label was pointing to something that is different size
+ break;
+ }
+ LabelInfo* m_info_next_next = m_info_next->next_addr_;
+ LabelInfo* p_info_next_next = p_info_next->next_addr_;
+ if (m_info_next_next && p_info_next_next) {
+ RVA m_rva_next = m_info_next_next->label_->rva_;
+ RVA p_rva_next = p_info_next_next->label_->rva_;
+ if (m_rva_next - m_rva != p_rva_next - p_rva) {
+ // Since following labels are no longer in address lockstep, assume
+ // this address has a difference.
+ break;
+ }
+ }
+
+ // The label has inconsistent numbers of references, it is probably not
+ // the same thing.
+ if (m_info_next->refs_ != p_info_next->refs_) {
+ break;
+ }
+
+ ALOG3 << " Extending assignment -> "
+ << ToString(p_info_next) << " := " << ToString(m_info_next);
+
+ AssignOne(p_info_next, m_info_next);
+
+ if (p_info_next->refs_ == m_info_next->refs_ &&
+ p_info_next->refs_ == 1) {
+ TryExtendSequence(p_info_next->positions_[0],
+ m_info_next->positions_[0]);
+ TryExtendSequenceBackwards(p_info_next->positions_[0],
+ m_info_next->positions_[0]);
+ }
+
+ p_info_next = p_info_next_next;
+ m_info_next = m_info_next_next;
+ }
+
+ LabelInfo* m_info_prev = m_info->prev_addr_;
+ LabelInfo* p_info_prev = p_info->prev_addr_;
+ for ( ; m_info_prev && p_info_prev; ) {
+ if (m_info_prev->assignment_)
+ break;
+
+ RVA m_rva = m_info_prev->label_->rva_;
+ RVA p_rva = p_info_prev->label_->rva_;
+
+ if (m_rva - m_rva_base != p_rva - p_rva_base) {
+ // previous label was pointing to something that is different size
+ break;
+ }
+ LabelInfo* m_info_prev_prev = m_info_prev->prev_addr_;
+ LabelInfo* p_info_prev_prev = p_info_prev->prev_addr_;
+
+ // The the label has inconsistent numbers of references, it is
+ // probably not the same thing
+ if (m_info_prev->refs_ != p_info_prev->refs_) {
+ break;
+ }
+
+ AssignOne(p_info_prev, m_info_prev);
+ ALOG3 << " Extending assignment <- " << ToString(p_info_prev) << " := "
+ << ToString(m_info_prev);
+
+ p_info_prev = p_info_prev_prev;
+ m_info_prev = m_info_prev_prev;
+ }
+ }
+
+ uint32 TryExtendSequence(uint32 p_pos_start, uint32 m_pos_start) {
+ uint32 p_pos = p_pos_start + 1;
+ uint32 m_pos = m_pos_start + 1;
+
+ while (p_pos < p_trace_.size() && m_pos < m_trace_.size()) {
+ LabelInfo* p_info = p_trace_[p_pos];
+ LabelInfo* m_info = m_trace_[m_pos];
+
+ // To match, either (1) both are assigned or (2) both are unassigned.
+ if ((p_info->assignment_ == NULL) != (m_info->assignment_ == NULL))
+ break;
+
+ // If they are assigned, it needs to be consistent (same index).
+ if (p_info->assignment_ && m_info->assignment_) {
+ if (p_info->label_->index_ != m_info->label_->index_)
+ break;
+ ++p_pos;
+ ++m_pos;
+ continue;
+ }
+
+ if (p_info->refs_ != m_info->refs_)
+ break;
+
+ AssignOne(p_info, m_info);
+ ALOG3 << " Extending assignment seq"
+ << "[+" << p_pos - p_pos_start << "]"
+ << " -> "
+ << ToString(p_info) << " := " << ToString(m_info);
+
+ ++p_pos;
+ ++m_pos;
+ }
+
+ return p_pos - p_pos_start;
+ }
+
+ uint32 TryExtendSequenceBackwards(uint32 p_pos_start, uint32 m_pos_start) {
+ if (p_pos_start == 0 || m_pos_start == 0)
+ return 0;
+
+ uint32 p_pos = p_pos_start - 1;
+ uint32 m_pos = m_pos_start - 1;
+
+ while (p_pos > 0 && m_pos > 0) {
+ LabelInfo* p_info = p_trace_[p_pos];
+ LabelInfo* m_info = m_trace_[m_pos];
+
+ if ((p_info->assignment_ == NULL) != (m_info->assignment_ == NULL))
+ break;
+
+ if (p_info->assignment_ && m_info->assignment_) {
+ if (p_info->label_->index_ != m_info->label_->index_)
+ break;
+ --p_pos;
+ --m_pos;
+ continue;
+ }
+
+ if (p_info->refs_ != m_info->refs_)
+ break;
+
+ AssignOne(p_info, m_info);
+ ALOG3 << " Extending assignment seq"
+ << "[-" << p_pos_start - p_pos << "]"
+ << " <- "
+ << ToString(p_info) << " := " << ToString(m_info);
+
+ --p_pos;
+ --m_pos;
+ }
+
+ return p_pos - p_pos_start;
+ }
+
+ Node* FindModelNode(Node* node) {
+ if (node->prev_ == NULL)
+ return m_root_;
+
+ Node* m_parent = FindModelNode(node->prev_);
+ if (m_parent == NULL) {
+ return NULL;
+ }
+
+ ExtendNode(m_parent, m_trace_);
+
+ LabelInfo* p_label = node->in_edge_;
+ LabelInfo* m_label = p_label->assignment_;
+ if (m_label == NULL) {
+ ALOG1 << "Expected assigned prefix";
+ return NULL;
+ }
+
+ Node::Edges::iterator e = m_parent->edges_.find(m_label);
+ if (e == m_parent->edges_.end()) {
+ ALOG2 << "Expected defined edge in parent";
+ return NULL;
+ }
+
+ return e->second;
+ }
+
+ Node* MakeRootNode(const Trace& trace) {
+ Node* node = new Node(NULL, NULL);
+ all_nodes_.push_back(node);
+ for (size_t i = 0; i < trace.size(); ++i) {
+ ++node->count_;
+ node->places_.push_back(i);
+ }
+ return node;
+ }
+
+ void ExtendNode(Node* node, const Trace& trace) {
+ // Make sure trie is filled in at this node.
+ if (node->Extended())
+ return;
+ for (size_t i = 0; i < node->places_.size(); ++i) {
+ uint32 index = node->places_.at(i);
+ if (index < trace.size()) {
+ LabelInfo* item = trace.at(index);
+ Node*& slot = node->edges_[item];
+ if (slot == NULL) {
+ slot = new Node(item, node);
+ all_nodes_.push_back(slot);
+ node->edges_in_frequency_order.push_back(slot);
+ }
+ slot->places_.push_back(index + 1);
+ ++slot->count_;
+ }
+ }
+ node->edges_in_frequency_order.sort(OrderNodeByCountDecreasing());
+ }
+
+ const Trace& m_trace_;
+ const Trace& p_trace_;
+ Node* m_root_;
+ Node* p_root_;
+
+ NodeQueue worklist_;
+ NodeQueue unsolved_;
+
+ std::vector<Node*> all_nodes_;
+
+ DISALLOW_COPY_AND_ASSIGN(AssignmentProblem);
+};
+
+class GraphAdjuster : public AdjustmentMethod {
+ public:
+ GraphAdjuster() {}
+ ~GraphAdjuster() {}
+
+ bool Adjust(const AssemblyProgram& model, AssemblyProgram* program) {
+ LOG(INFO) << "GraphAdjuster::Adjust";
+ prog_ = program;
+ model_ = &model;
+ debug_label_index_gen_ = 0;
+ return Finish();
+ }
+
+ bool Finish() {
+ prog_->UnassignIndexes();
+ CollectTraces(model_, &model_abs32_, &model_rel32_, true);
+ CollectTraces(prog_, &prog_abs32_, &prog_rel32_, false);
+ Solve(model_abs32_, prog_abs32_);
+ Solve(model_rel32_, prog_rel32_);
+ prog_->AssignRemainingIndexes();
+ return true;
+ }
+
+ private:
+
+ void CollectTraces(const AssemblyProgram* program, Trace* abs32, Trace* rel32,
+ bool is_model) {
+ const std::vector<Instruction*>& instructions = program->instructions();
+ for (size_t i = 0; i < instructions.size(); ++i) {
+ Instruction* instruction = instructions.at(i);
+ if (Label* label = program->InstructionAbs32Label(instruction))
+ ReferenceLabel(abs32, label, is_model);
+ if (Label* label = program->InstructionRel32Label(instruction))
+ ReferenceLabel(rel32, label, is_model);
+ }
+ // TODO(sra): we could simply append all the labels in index order to
+ // incorporate some costing for entropy (bigger deltas) that will be
+ // introduced into the label address table by non-monotonic ordering. This
+ // would have some knock-on effects to parts of the algorithm that work on
+ // single-occurence labels.
+ }
+
+ void Solve(const Trace& model, const Trace& problem) {
+ LinkLabelInfos(model);
+ LinkLabelInfos(problem);
+ AssignmentProblem a(model, problem);
+ a.Solve();
+ }
+
+ void LinkLabelInfos(const Trace& trace) {
+ typedef std::set<LabelInfo*, OrderLabelInfoByAddressAscending> Ordered;
+ Ordered ordered;
+ for (Trace::const_iterator p = trace.begin(); p != trace.end(); ++p)
+ ordered.insert(*p);
+ LabelInfo* prev = NULL;
+ for (Ordered::iterator p = ordered.begin(); p != ordered.end(); ++p) {
+ LabelInfo* curr = *p;
+ if (prev) prev->next_addr_ = curr;
+ curr->prev_addr_ = prev;
+ prev = curr;
+
+ if (curr->positions_.size() != curr->refs_)
+ NOTREACHED();
+ }
+ }
+
+ void ReferenceLabel(Trace* trace, Label* label, bool is_model) {
+ trace->push_back(MakeLabelInfo(label, is_model, trace->size()));
+ }
+
+ LabelInfo* MakeLabelInfo(Label* label, bool is_model, uint32 position) {
+ LabelInfo& slot = label_infos_[label];
+ if (slot.label_ == NULL) {
+ slot.label_ = label;
+ slot.is_model_ = is_model;
+ slot.debug_index_ = ++debug_label_index_gen_;
+ }
+ slot.positions_.push_back(position);
+ ++slot.refs_;
+ return &slot;
+ }
+
+ AssemblyProgram* prog_; // Program to be adjusted, owned by caller.
+ const AssemblyProgram* model_; // Program to be mimicked, owned by caller.
+
+ Trace model_abs32_;
+ Trace model_rel32_;
+ Trace prog_abs32_;
+ Trace prog_rel32_;
+
+ int debug_label_index_gen_;
+
+ // Note LabelInfo is allocated inside map, so the LabelInfo lifetimes are
+ // managed by the map.
+ std::map<Label*, LabelInfo> label_infos_;
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(GraphAdjuster);
+};
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+void AdjustmentMethod::Destroy() { delete this; }
+
+AdjustmentMethod* AdjustmentMethod::MakeNullAdjustmentMethod() {
+ return new NullAdjustmentMethod();
+}
+
+AdjustmentMethod* AdjustmentMethod::MakeProductionAdjustmentMethod() {
+ return new GraphAdjuster();
+}
+
+Status Adjust(const AssemblyProgram& model, AssemblyProgram* program) {
+ AdjustmentMethod* method = AdjustmentMethod::MakeProductionAdjustmentMethod();
+ bool ok = method->Adjust(model, program);
+ method->Destroy();
+ if (ok)
+ return C_OK;
+ else
+ return C_ADJUSTMENT_FAILED;
+}
+
+} // namespace courgette
diff --git a/third_party/courgette/adjustment_method.h b/third_party/courgette/adjustment_method.h new file mode 100644 index 0000000..2a5b0c7 --- /dev/null +++ b/third_party/courgette/adjustment_method.h @@ -0,0 +1,43 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef COURGETTE_ADJUSTMENT_METHOD_H_
+#define COURGETTE_ADJUSTMENT_METHOD_H_
+
+#include "base/basictypes.h"
+
+namespace courgette {
+
+class AssemblyProgram;
+
+class AdjustmentMethod {
+ public:
+ // Factory methods for making adjusters.
+
+ // Returns the adjustment method used in production.
+ static AdjustmentMethod* MakeProductionAdjustmentMethod();
+
+ // Returns and adjustement method that makes no adjustments.
+ static AdjustmentMethod* MakeNullAdjustmentMethod();
+
+
+ // Adjusts |program| to increase similarity to |model|. |program| can be
+ // changed in any way provided that it still produces the same output when
+ // assembled.
+ virtual bool Adjust(const AssemblyProgram& model,
+ AssemblyProgram* program) = 0;
+
+ // Deletes 'this' adjustment method.
+ virtual void Destroy();
+
+ protected:
+ AdjustmentMethod() {}
+ virtual ~AdjustmentMethod() {}
+
+ DISALLOW_COPY_AND_ASSIGN(AdjustmentMethod);
+};
+
+} // namespace courgette
+#endif // COURGETTE_ADJUSTMENT_METHOD_H_
+
diff --git a/third_party/courgette/adjustment_method_unittest.cc b/third_party/courgette/adjustment_method_unittest.cc new file mode 100644 index 0000000..2048126 --- /dev/null +++ b/third_party/courgette/adjustment_method_unittest.cc @@ -0,0 +1,109 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <string>
+
+#include "base/path_service.h"
+#include "base/file_util.h"
+#include "base/string_util.h"
+
+#include "third_party/courgette/assembly_program.h"
+#include "third_party/courgette/courgette.h"
+#include "third_party/courgette/streams.h"
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+class AdjustmentMethodTest : public testing::Test {
+ public:
+ void Test1() const;
+
+ private:
+ void SetUp() {
+ }
+
+ void TearDown() {
+ }
+
+ // Returns one of two similar a simple programs. They differ only in the
+ // label assignment, so that it is possible to make them look identical.
+ courgette::AssemblyProgram* MakeProgram(int kind) const {
+ courgette::AssemblyProgram* prog = new courgette::AssemblyProgram();
+ prog->set_image_base(0x00400000);
+
+ courgette::Label* labelA = prog->FindOrMakeAbs32Label(0x00410000);
+ courgette::Label* labelB = prog->FindOrMakeAbs32Label(0x00410004);
+
+ prog->EmitAbs32(labelA);
+ prog->EmitAbs32(labelA);
+ prog->EmitAbs32(labelB);
+ prog->EmitAbs32(labelA);
+ prog->EmitAbs32(labelA);
+ prog->EmitAbs32(labelB);
+
+ if (kind == 0) {
+ labelA->index_ = 0;
+ labelB->index_ = 1;
+ } else {
+ labelA->index_ = 1;
+ labelB->index_ = 0;
+ }
+ prog->AssignRemainingIndexes();
+
+ return prog;
+ }
+
+ courgette::AssemblyProgram* MakeProgramA() const { return MakeProgram(0); }
+ courgette::AssemblyProgram* MakeProgramB() const { return MakeProgram(1); }
+
+ // Returns a string that is the serialized version of |program|.
+ // Deletes |program|.
+ std::string Serialize(courgette::AssemblyProgram *program) const {
+ courgette::EncodedProgram* encoded = NULL;
+
+ const courgette::Status encode_status = Encode(program, &encoded);
+ EXPECT_EQ(courgette::C_OK, encode_status);
+
+ DeleteAssemblyProgram(program);
+
+ courgette::SinkStreamSet sinks;
+ const courgette::Status write_status = WriteEncodedProgram(encoded, &sinks);
+ EXPECT_EQ(courgette::C_OK, write_status);
+
+ DeleteEncodedProgram(encoded);
+
+ courgette::SinkStream sink;
+ bool can_collect = sinks.CopyTo(&sink);
+ EXPECT_TRUE(can_collect);
+
+ return std::string(reinterpret_cast<const char *>(sink.Buffer()),
+ sink.Length());
+ }
+};
+
+
+void AdjustmentMethodTest::Test1() const {
+ courgette::AssemblyProgram* prog1 = MakeProgramA();
+ courgette::AssemblyProgram* prog2 = MakeProgramB();
+ std::string s1 = Serialize(prog1);
+ std::string s2 = Serialize(prog2);
+
+ // Don't use EXPECT_EQ because strings are unprintable.
+ EXPECT_FALSE(s1 == s2); // Unadjusted A and B differ.
+
+ courgette::AssemblyProgram* prog5 = MakeProgramA();
+ courgette::AssemblyProgram* prog6 = MakeProgramB();
+ courgette::Status can_adjust = Adjust(*prog5, prog6);
+ EXPECT_EQ(courgette::C_OK, can_adjust);
+ std::string s5 = Serialize(prog5);
+ std::string s6 = Serialize(prog6);
+
+ EXPECT_TRUE(s1 == s5); // Adjustment did not change A (prog5)
+ EXPECT_TRUE(s5 == s6); // Adjustment did change B into A
+}
+
+
+TEST_F(AdjustmentMethodTest, All) {
+ Test1();
+}
+
diff --git a/third_party/courgette/assembly_program.cc b/third_party/courgette/assembly_program.cc new file mode 100644 index 0000000..178dfdf --- /dev/null +++ b/third_party/courgette/assembly_program.cc @@ -0,0 +1,373 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "third_party/courgette/assembly_program.h"
+
+#include <memory.h>
+#include <algorithm>
+#include <map>
+#include <set>
+#include <sstream>
+#include <vector>
+
+#include "base/logging.h"
+
+#include "third_party/courgette/courgette.h"
+#include "third_party/courgette/encoded_program.h"
+
+namespace courgette {
+
+// Opcodes of simple assembly language
+enum OP {
+ ORIGIN, // ORIGIN <rva> - set current address for assembly.
+ MAKERELOCS, // Generates a base relocation table.
+ DEFBYTE, // DEFBYTE <value> - emit a byte literal.
+ REL32, // REL32 <label> - emit a rel32 encoded reference to 'label'.
+ ABS32, // REL32 <label> - emit am abs32 encoded reference to 'label'.
+ LAST_OP
+};
+
+// Base class for instructions. Because we have so many instructions we want to
+// keep them as small as possible. For this reason we avoid virtual functions.
+//
+class Instruction {
+ public:
+ OP op() const { return static_cast<OP>(op_); }
+
+ protected:
+ explicit Instruction(OP op) : op_(op), info_(0) {}
+ Instruction(OP op, unsigned int info) : op_(op), info_(info) {}
+
+ uint32 op_ : 4; // A few bits to store the OP code.
+ uint32 info_ : 28; // Remaining bits in first word available to subclass.
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(Instruction);
+};
+
+namespace {
+
+// Sets the current address for the emitting instructions.
+class OriginInstruction : public Instruction {
+ public:
+ explicit OriginInstruction(RVA rva) : Instruction(ORIGIN, 0), rva_(rva) {}
+ RVA origin_rva() const { return rva_; }
+ private:
+ RVA rva_;
+};
+
+// Emits an entire base relocation table.
+class MakeRelocsInstruction : public Instruction {
+ public:
+ MakeRelocsInstruction() : Instruction(MAKERELOCS) {}
+};
+
+// Emits a single byte.
+class ByteInstruction : public Instruction {
+ public:
+ explicit ByteInstruction(uint8 value) : Instruction(DEFBYTE, value) {}
+ uint8 byte_value() const { return info_; }
+};
+
+// A ABS32 to REL32 instruction emits a reference to a label's address.
+class InstructionWithLabel : public Instruction {
+ public:
+ InstructionWithLabel(OP op, Label* label)
+ : Instruction(op, 0), label_(label) {
+ if (label == NULL) NOTREACHED();
+ }
+ Label* label() const { return label_; }
+ private:
+ Label* label_;
+};
+
+} // namespace
+
+AssemblyProgram::AssemblyProgram()
+ : image_base_(0),
+ byte_instruction_cache_(NULL) {
+}
+
+static void DeleteContainedLabels(const RVAToLabel& labels) {
+ for (RVAToLabel::const_iterator p = labels.begin(); p != labels.end(); ++p)
+ delete p->second;
+}
+
+AssemblyProgram::~AssemblyProgram() {
+ for (size_t i = 0; i < instructions_.size(); ++i) {
+ Instruction* instruction = instructions_[i];
+ if (instruction->op() != DEFBYTE) // Will be in byte_instruction_cache_.
+ delete instruction;
+ }
+ if (byte_instruction_cache_) {
+ for (size_t i = 0; i < 256; ++i)
+ delete byte_instruction_cache_[i];
+ delete[] byte_instruction_cache_;
+ }
+ DeleteContainedLabels(rel32_labels_);
+ DeleteContainedLabels(abs32_labels_);
+}
+
+void AssemblyProgram::EmitMakeRelocsInstruction() {
+ Emit(new MakeRelocsInstruction());
+}
+
+void AssemblyProgram::EmitOriginInstruction(RVA rva) {
+ Emit(new OriginInstruction(rva));
+}
+
+void AssemblyProgram::EmitByteInstruction(uint8 byte) {
+ Emit(GetByteInstruction(byte));
+}
+
+void AssemblyProgram::EmitRel32(Label* label) {
+ Emit(new InstructionWithLabel(REL32, label));
+}
+
+void AssemblyProgram::EmitAbs32(Label* label) {
+ Emit(new InstructionWithLabel(ABS32, label));
+}
+
+Label* AssemblyProgram::FindOrMakeAbs32Label(RVA rva) {
+ return FindLabel(rva, &abs32_labels_);
+}
+
+Label* AssemblyProgram::FindOrMakeRel32Label(RVA rva) {
+ return FindLabel(rva, &rel32_labels_);
+}
+
+void AssemblyProgram::DefaultAssignIndexes() {
+ DefaultAssignIndexes(&abs32_labels_);
+ DefaultAssignIndexes(&rel32_labels_);
+}
+
+void AssemblyProgram::UnassignIndexes() {
+ UnassignIndexes(&abs32_labels_);
+ UnassignIndexes(&rel32_labels_);
+}
+
+void AssemblyProgram::AssignRemainingIndexes() {
+ AssignRemainingIndexes(&abs32_labels_);
+ AssignRemainingIndexes(&rel32_labels_);
+}
+
+Label* AssemblyProgram::InstructionAbs32Label(
+ const Instruction* instruction) const {
+ if (instruction->op() == ABS32)
+ return static_cast<const InstructionWithLabel*>(instruction)->label();
+ return NULL;
+}
+
+Label* AssemblyProgram::InstructionRel32Label(
+ const Instruction* instruction) const {
+ if (instruction->op() == REL32)
+ return static_cast<const InstructionWithLabel*>(instruction)->label();
+ return NULL;
+}
+
+Label* AssemblyProgram::FindLabel(RVA rva, RVAToLabel* labels) {
+ Label*& slot = (*labels)[rva];
+ if (slot == 0) {
+ slot = new Label(rva);
+ }
+ return slot;
+}
+
+void AssemblyProgram::UnassignIndexes(RVAToLabel* labels) {
+ for (RVAToLabel::iterator p = labels->begin(); p != labels->end(); ++p) {
+ Label* current = p->second;
+ current->index_ = Label::kNoIndex;
+ }
+}
+
+// DefaultAssignIndexes takes a set of labels and assigns indexes in increasing
+// address order.
+//
+void AssemblyProgram::DefaultAssignIndexes(RVAToLabel* labels) {
+ int index = 0;
+ for (RVAToLabel::iterator p = labels->begin(); p != labels->end(); ++p) {
+ Label* current = p->second;
+ if (current->index_ != Label::kNoIndex)
+ NOTREACHED();
+ current->index_ = index;
+ ++index;
+ }
+}
+
+// AssignRemainingIndexes assigns indexes to any addresses (labels) that are not
+// yet assigned an index.
+//
+void AssemblyProgram::AssignRemainingIndexes(RVAToLabel* labels) {
+ // An address table compresses best when each index is associated with an
+ // address that is slight larger than the previous index.
+
+ // First see which indexes have not been used. The 'available' vector could
+ // grow even bigger, but the number of addresses is a better starting size
+ // than empty.
+ std::vector<bool> available(labels->size(), true);
+ int used = 0;
+
+ for (RVAToLabel::iterator p = labels->begin(); p != labels->end(); ++p) {
+ size_t index = p->second->index_;
+ if (index != Label::kNoIndex) {
+ while (index >= available.size())
+ available.push_back(true);
+ available.at(index) = false;
+ ++used;
+ }
+ }
+
+ LOG(INFO) << used << " of " << labels->size() << " labels pre-assigned";
+
+ // Are there any unused labels that happen to be adjacent following a used
+ // label?
+ //
+ int fill_forward_count = 0;
+ Label* prev = 0;
+ for (RVAToLabel::iterator p = labels->begin(); p != labels->end(); ++p) {
+ Label* current = p->second;
+ if (current->index_ == Label::kNoIndex) {
+ size_t index = 0;
+ if (prev && prev->index_ != Label::kNoIndex)
+ index = prev->index_ + 1;
+ if (index < available.size() && available.at(index)) {
+ current->index_ = index;
+ available.at(index) = false;
+ ++fill_forward_count;
+ }
+ }
+ prev = current;
+ }
+
+ // Are there any unused labels that happen to be adjacent preceeding a used
+ // label?
+ //
+ int fill_backward_count = 0;
+ int backward_refs = 0;
+ prev = 0;
+ for (RVAToLabel::reverse_iterator p = labels->rbegin();
+ p != labels->rend();
+ ++p) {
+ Label* current = p->second;
+ if (current->index_ == Label::kNoIndex) {
+ int prev_index;
+ if (prev)
+ prev_index = prev->index_;
+ else
+ prev_index = available.size();
+ if (prev_index != 0 &&
+ prev_index != Label::kNoIndex &&
+ available.at(prev_index - 1)) {
+ current->index_ = prev_index - 1;
+ available.at(current->index_) = false;
+ ++fill_backward_count;
+ }
+ }
+ prev = current;
+ }
+
+ // Fill in any remaining indexes
+ int fill_infill_count = 0;
+ int index = 0;
+ for (RVAToLabel::iterator p = labels->begin(); p != labels->end(); ++p) {
+ Label* current = p->second;
+ if (current->index_ == Label::kNoIndex) {
+ while (!available.at(index)) {
+ ++index;
+ }
+ current->index_ = index;
+ available.at(index) = false;
+ ++index;
+ ++fill_infill_count;
+ }
+ }
+
+ LOG(INFO) << " fill"
+ << " forward " << fill_forward_count << " "
+ << " backward " << fill_backward_count << " "
+ << " infill " << fill_infill_count;
+}
+
+typedef void (EncodedProgram::*DefineLabelMethod)(int index, RVA value);
+
+static void DefineLabels(const RVAToLabel& labels,
+ EncodedProgram* encoded_format,
+ DefineLabelMethod define_label) {
+ for (RVAToLabel::const_iterator p = labels.begin(); p != labels.end(); ++p) {
+ Label* label = p->second;
+ (encoded_format->*define_label)(label->index_, label->rva_);
+ }
+}
+
+EncodedProgram* AssemblyProgram::Encode() const {
+ EncodedProgram* encoded = new EncodedProgram();
+
+ encoded->set_image_base(image_base_);
+ DefineLabels(abs32_labels_, encoded, &EncodedProgram::DefineAbs32Label);
+ DefineLabels(rel32_labels_, encoded, &EncodedProgram::DefineRel32Label);
+ encoded->EndLabels();
+
+ for (size_t i = 0; i < instructions_.size(); ++i) {
+ Instruction* instruction = instructions_[i];
+
+ switch (instruction->op()) {
+ case ORIGIN: {
+ OriginInstruction* org = static_cast<OriginInstruction*>(instruction);
+ encoded->AddOrigin(org->origin_rva());
+ break;
+ }
+ case DEFBYTE: {
+ uint8 b = static_cast<ByteInstruction*>(instruction)->byte_value();
+ encoded->AddCopy(1, &b);
+ break;
+ }
+ case REL32: {
+ Label* label = static_cast<InstructionWithLabel*>(instruction)->label();
+ encoded->AddRel32(label->index_);
+ break;
+ }
+ case ABS32: {
+ Label* label = static_cast<InstructionWithLabel*>(instruction)->label();
+ encoded->AddAbs32(label->index_);
+ break;
+ }
+ case MAKERELOCS: {
+ encoded->AddMakeRelocs();
+ break;
+ }
+ default: {
+ NOTREACHED() << "Unknown Insn OP kind";
+ }
+ }
+ }
+
+ return encoded;
+}
+
+Instruction* AssemblyProgram::GetByteInstruction(uint8 byte) {
+ if (!byte_instruction_cache_) {
+ byte_instruction_cache_ = new Instruction*[256];
+ for (int i = 0; i < 256; ++i) {
+ byte_instruction_cache_[i] = new ByteInstruction(static_cast<uint8>(i));
+ }
+ }
+
+ return byte_instruction_cache_[byte];
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+Status Encode(AssemblyProgram* program, EncodedProgram** output) {
+ *output = NULL;
+ EncodedProgram *encoded = program->Encode();
+ if (encoded) {
+ *output = encoded;
+ return C_OK;
+ } else {
+ return C_GENERAL_ERROR;
+ }
+}
+
+} // namespace courgette
+
diff --git a/third_party/courgette/assembly_program.h b/third_party/courgette/assembly_program.h new file mode 100644 index 0000000..4b48133 --- /dev/null +++ b/third_party/courgette/assembly_program.h @@ -0,0 +1,134 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef COURGETTE_ASSEMBLY_PROGRAM_H_
+#define COURGETTE_ASSEMBLY_PROGRAM_H_
+
+#include <map>
+#include <set>
+#include <vector>
+
+#include "base/basictypes.h"
+
+#include "third_party/courgette/image_info.h"
+
+namespace courgette {
+
+class EncodedProgram;
+class Instruction;
+
+// A Label is a symbolic reference to an address. Unlike a conventional
+// assembly language, we always know the address. The address will later be
+// stored in a table and the Label will be replaced with the index into the
+// table.
+//
+// TODO(sra): Make fields private and add setters and getters.
+class Label {
+ public:
+ static const int kNoIndex = -1;
+ Label() : rva_(0), index_(kNoIndex) {}
+ explicit Label(RVA rva) : rva_(rva), index_(kNoIndex) {}
+
+ RVA rva_; // Address refered to by the label.
+ int index_; // Index of address in address table, kNoIndex until assigned.
+};
+
+typedef std::map<RVA, Label*> RVAToLabel;
+
+// An AssemblyProgram is the result of disassembling an executable file.
+//
+// * The disassembler creates labels in the AssemblyProgram and emits
+// 'Instructions'.
+// * The disassembler then calls DefaultAssignIndexes to assign
+// addresses to positions in the address tables.
+// * [Optional step]
+// * At this point the AssemblyProgram can be converted into an
+// EncodedProgram and serialized to an output stream.
+// * Later, the EncodedProgram can be deserialized and assembled into
+// the original file.
+//
+// The optional step is to modify the AssemblyProgram. One form of modification
+// is to assign indexes in such a way as to make the EncodedProgram for this
+// AssemblyProgram look more like the EncodedProgram for some other
+// AssemblyProgram. The modification process should call UnassignIndexes, do
+// its own assignment, and then call AssignRemainingIndexes to ensure all
+// indexes are assigned.
+//
+class AssemblyProgram {
+ public:
+ AssemblyProgram();
+ ~AssemblyProgram();
+
+ void set_image_base(uint64 image_base) { image_base_ = image_base; }
+
+ // Instructions will be assembled in the order they are emitted.
+
+ // Generates an entire base relocation table.
+ void EmitMakeRelocsInstruction();
+
+ // Following instruction will be assembled at address 'rva'.
+ void EmitOriginInstruction(RVA rva);
+
+ // Generates a single byte of data or machine instruction.
+ void EmitByteInstruction(uint8 byte);
+
+ // Generates 4-byte relative reference to address of 'label'.
+ void EmitRel32(Label* label);
+
+ // Generates 4-byte absolute reference to address of 'label'.
+ void EmitAbs32(Label* label);
+
+ Label* FindOrMakeAbs32Label(RVA rva);
+ Label* FindOrMakeRel32Label(RVA rva);
+
+ void DefaultAssignIndexes();
+ void UnassignIndexes();
+ void AssignRemainingIndexes();
+
+ EncodedProgram* Encode() const;
+
+ // Accessor for instruction list.
+ const std::vector<Instruction*>& instructions() const {
+ return instructions_;
+ }
+
+ // Returns the label if the instruction contains and absolute address,
+ // otherwise returns NULL.
+ Label* InstructionAbs32Label(const Instruction* instruction) const;
+
+ // Returns the label if the instruction contains and rel32 offset,
+ // otherwise returns NULL.
+ Label* InstructionRel32Label(const Instruction* instruction) const;
+
+
+ private:
+ void Emit(Instruction* instruction) { instructions_.push_back(instruction); }
+
+ Label* FindLabel(RVA rva, RVAToLabel* labels);
+
+ // Helper methods for the public versions.
+ static void UnassignIndexes(RVAToLabel* labels);
+ static void DefaultAssignIndexes(RVAToLabel* labels);
+ static void AssignRemainingIndexes(RVAToLabel* labels);
+
+ // Sharing instructions that emit a single byte saves a lot of space.
+ Instruction* GetByteInstruction(uint8 byte);
+ Instruction** byte_instruction_cache_;
+
+ uint64 image_base_; // Desired or mandated base address of image.
+
+ std::vector<Instruction*> instructions_; // All the instructions in program.
+
+ // These are lookup maps to find the label associated with a given address.
+ // We have separate label spaces for addresses referenced by rel32 labels and
+ // abs32 labels. This is somewhat arbitrary.
+ RVAToLabel rel32_labels_;
+ RVAToLabel abs32_labels_;
+
+ DISALLOW_COPY_AND_ASSIGN(AssemblyProgram);
+};
+
+} // namespace courgette
+#endif // COURGETTE_ASSEMBLY_PROGRAM_H_
+
diff --git a/third_party/courgette/bsdiff.h b/third_party/courgette/bsdiff.h new file mode 100644 index 0000000..bf7fdec --- /dev/null +++ b/third_party/courgette/bsdiff.h @@ -0,0 +1,87 @@ +/*- + * Copyright 2003,2004 Colin Percival + * All rights reserved + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted providing that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + * Changelog: + * 2005-04-26 - Define the header as a C structure, add a CRC32 checksum to + * the header, and make all the types 32-bit. + * --Benjamin Smedberg <benjamin@smedbergs.us> + * 2009-03-31 - Change to use Streams. Move CRC code to crc.{h,cc} + * Changed status to an enum, removed unused status codes. + * --Stephen Adams <sra@chromium.org> + */ + +#ifndef COURGETTE_BSDIFF_H_ +#define COURGETTE_BSDIFF_H_ + +#include "base/basictypes.h" + +namespace courgette { + +enum BSDiffStatus { + OK = 0, + MEM_ERROR = 1, + CRC_ERROR = 2, + READ_ERROR = 3, + UNEXPECTED_ERROR = 4 +}; + +class SourceStream; +class SinkStream; + +// Creates a binary patch. +// +BSDiffStatus CreateBinaryPatch(SourceStream* old_stream, + SourceStream* new_stream, + SinkStream* patch_stream); + +// Applies the given patch file to a given source file. This method validates +// the CRC of the original file stored in the patch file, before applying the +// patch to it. +// +BSDiffStatus ApplyBinaryPatch(SourceStream* old_stream, + SourceStream* patch_stream, + SinkStream* new_stream); + + +// The following declarations are common to the patch-creation and +// patch-application code. + +// The patch stream starts with a MBSPatchHeader. +typedef struct MBSPatchHeader_ { + char tag[8]; // Contains MBS_PATCH_HEADER_TAG + uint32 slen; // Length of the file to be patched. + uint32 scrc32; // CRC32 of the file to be patched. + uint32 dlen; // Length of the result file. + uint32 cblen; // Length of the control block in bytes. + uint32 difflen; // Length of the diff block in bytes. + uint32 extralen; // Length of the extra block in bytes. +} MBSPatchHeader; + +// This is the value for the tag field. Must match length exactly, not counting +// null at end of string. +#define MBS_PATCH_HEADER_TAG "GBSDIF42" + +} // namespace +#endif // COURGETTE_BSDIFF_H_ diff --git a/third_party/courgette/bsdiff_apply.cc b/third_party/courgette/bsdiff_apply.cc new file mode 100644 index 0000000..f45ae14 --- /dev/null +++ b/third_party/courgette/bsdiff_apply.cc @@ -0,0 +1,165 @@ +/*- + * Copyright 2003,2004 Colin Percival + * All rights reserved + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted providing that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + * Changelog: + * 2009-03-31 - Change to use Streams. Move CRC code to crc.{h,cc} + * --Stephen Adams <sra@chromium.org> + */ + +// Copyright (c) 2009 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "third_party/courgette/bsdiff.h" + +#include "third_party/courgette/crc.h" +#include "third_party/courgette/streams.h" + +namespace courgette { + +BSDiffStatus MBS_ReadHeader(SourceStream* stream, MBSPatchHeader* header) { + if (!stream->Read(header->tag, sizeof(header->tag))) return READ_ERROR; + if (!stream->ReadVarint32(&header->slen)) return READ_ERROR; + if (!stream->ReadVarint32(&header->scrc32)) return READ_ERROR; + if (!stream->ReadVarint32(&header->dlen)) return READ_ERROR; + if (!stream->ReadVarint32(&header->cblen)) return READ_ERROR; + if (!stream->ReadVarint32(&header->difflen)) return READ_ERROR; + if (!stream->ReadVarint32(&header->extralen)) return READ_ERROR; + + // The string will have a NUL terminator that we don't use, hence '-1'. + COMPILE_ASSERT(sizeof(MBS_PATCH_HEADER_TAG) - 1 == sizeof(header->tag), + MBS_PATCH_HEADER_TAG_must_match_header_field_size); + if (memcmp(header->tag, MBS_PATCH_HEADER_TAG, 8) != 0) + return UNEXPECTED_ERROR; + + size_t bytes_remaining = stream->Remaining(); + if (header->cblen + + header->difflen + + header->extralen != bytes_remaining) + return UNEXPECTED_ERROR; + + return OK; +} + +BSDiffStatus MBS_ApplyPatch(const MBSPatchHeader *header, + SourceStream* patch_stream, + const uint8* old_start, size_t old_size, + SinkStream* new_stream) { + const uint8* old_end = old_start + old_size; + + SourceStream control_stream; + + const uint8* control_start = patch_stream->Buffer(); + if (!patch_stream->ReadSubstream(header->cblen, &control_stream)) + return READ_ERROR; + if (!patch_stream->Skip(header->difflen + header->extralen)) + return READ_ERROR; + if (!patch_stream->Empty()) + return READ_ERROR; + + const uint8* diff_start = control_start + header->cblen; + const uint8* diff_end = diff_start + header->difflen; + const uint8* extra_start = diff_end; + const uint8* extra_end = extra_start + header->extralen; + + const uint8* old_position = old_start; + const uint8* diff_position = diff_start; + const uint8* extra_position = extra_start; + + new_stream->Reserve(header->dlen); + + while (!control_stream.Empty()) { + uint32 copy_count, extra_count; + int32 seek_adjustment; + if (!control_stream.ReadVarint32(©_count)) + return UNEXPECTED_ERROR; + if (!control_stream.ReadVarint32(&extra_count)) + return UNEXPECTED_ERROR; + if (!control_stream.ReadVarint32Signed(&seek_adjustment)) + return UNEXPECTED_ERROR; + +#ifdef DEBUG_bsmedberg + printf("Applying block: copy: %-8u extra: %-8u seek: %+i\n", + copy_count, extra_count, seek_adjustment); +#endif + // Byte-wise arithmetically add bytes from old file to bytes from the diff + // block. + if (copy_count > static_cast<size_t>(old_end - old_position)) + return UNEXPECTED_ERROR; + if (copy_count > static_cast<size_t>(diff_end - diff_position)) + return UNEXPECTED_ERROR; + + // Add together bytes from the 'old' file and the 'diff' stream. + for (size_t i = 0; i < copy_count; ++i) { + uint8 byte = old_position[i] + diff_position[i]; + new_stream->Write(&byte, 1); + } + old_position += copy_count; + diff_position += copy_count; + + // Copy bytes from the extra block. + if (extra_count > static_cast<size_t>(extra_end - extra_position)) + return UNEXPECTED_ERROR; + + new_stream->Write(extra_position, extra_count); + extra_position += extra_count; + + // "seek" forwards (or backwards) in oldfile. + if (old_position + seek_adjustment < old_start || + old_position + seek_adjustment > old_end) + return UNEXPECTED_ERROR; + + old_position += seek_adjustment; + } + + if (diff_position != diff_end) + return UNEXPECTED_ERROR; + if (extra_position != extra_end) + return UNEXPECTED_ERROR; + + return OK; +} + +BSDiffStatus ApplyBinaryPatch(SourceStream* old_stream, + SourceStream* patch_stream, + SinkStream* new_stream) { + MBSPatchHeader header; + BSDiffStatus ret = MBS_ReadHeader(patch_stream, &header); + if (ret != OK) return ret; + + const uint8* old_start = old_stream->Buffer(); + size_t old_size = old_stream->Remaining(); + + if (old_size != header.slen) return UNEXPECTED_ERROR; + + if (CalculateCrc(old_start, old_size) != header.scrc32) + return CRC_ERROR; + + MBS_ApplyPatch(&header, patch_stream, old_start, old_size, new_stream); + + return OK; +} + +} // namespace diff --git a/third_party/courgette/bsdiff_create.cc b/third_party/courgette/bsdiff_create.cc new file mode 100644 index 0000000..cdd6cb6 --- /dev/null +++ b/third_party/courgette/bsdiff_create.cc @@ -0,0 +1,432 @@ +/* + bsdiff.c -- Binary patch generator. + + Copyright 2003 Colin Percival + + For the terms under which this work may be distributed, please see + the adjoining file "LICENSE". + + ChangeLog: + 2005-05-05 - Use the modified header struct from bspatch.h; use 32-bit + values throughout. + --Benjamin Smedberg <benjamin@smedbergs.us> + 2005-05-18 - Use the same CRC algorithm as bzip2, and leverage the CRC table + provided by libbz2. + --Darin Fisher <darin@meer.net> + 2007-11-14 - Changed to use Crc from Lzma library instead of Bzip library + --Rahul Kuchhal + 2009-03-31 - Change to use Streams. Added lots of comments. + --Stephen Adams <sra@chromium.org> +*/ + +#include "third_party/courgette/bsdiff.h" + +#include <stdlib.h> +#include <algorithm> + +#include "base/logging.h" +#include "base/scoped_ptr.h" +#include "base/string_util.h" +#include "base/time.h" + +#include "third_party/courgette/crc.h" +#include "third_party/courgette/streams.h" + +namespace courgette { + +// ------------------------------------------------------------------------ +// +// The following code is taken verbatim from 'bsdiff.c'. Please keep all the +// code formatting and variable names. The only changes from the original are +// replacing tabs with spaces, indentation, and using 'const'. +// +// The code appears to be a rewritten version of the suffix array algorithm +// presented in "Faster Suffix Sorting" by N. Jesper Larsson and Kunihiko +// Sadakane, special-cased for bytes. + +static void +split(int *I,int *V,int start,int len,int h) +{ + int i,j,k,x,tmp,jj,kk; + + if(len<16) { + for(k=start;k<start+len;k+=j) { + j=1;x=V[I[k]+h]; + for(i=1;k+i<start+len;i++) { + if(V[I[k+i]+h]<x) { + x=V[I[k+i]+h]; + j=0; + }; + if(V[I[k+i]+h]==x) { + tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp; + j++; + }; + }; + for(i=0;i<j;i++) V[I[k+i]]=k+j-1; + if(j==1) I[k]=-1; + }; + return; + }; + + x=V[I[start+len/2]+h]; + jj=0;kk=0; + for(i=start;i<start+len;i++) { + if(V[I[i]+h]<x) jj++; + if(V[I[i]+h]==x) kk++; + }; + jj+=start;kk+=jj; + + i=start;j=0;k=0; + while(i<jj) { + if(V[I[i]+h]<x) { + i++; + } else if(V[I[i]+h]==x) { + tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp; + j++; + } else { + tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp; + k++; + }; + }; + + while(jj+j<kk) { + if(V[I[jj+j]+h]==x) { + j++; + } else { + tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp; + k++; + }; + }; + + if(jj>start) split(I,V,start,jj-start,h); + + for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1; + if(jj==kk-1) I[jj]=-1; + + if(start+len>kk) split(I,V,kk,start+len-kk,h); +} + +static void +qsufsort(int *I,int *V,const unsigned char *old,int oldsize) +{ + int buckets[256]; + int i,h,len; + + for(i=0;i<256;i++) buckets[i]=0; + for(i=0;i<oldsize;i++) buckets[old[i]]++; + for(i=1;i<256;i++) buckets[i]+=buckets[i-1]; + for(i=255;i>0;i--) buckets[i]=buckets[i-1]; + buckets[0]=0; + + for(i=0;i<oldsize;i++) I[++buckets[old[i]]]=i; + I[0]=oldsize; + for(i=0;i<oldsize;i++) V[i]=buckets[old[i]]; + V[oldsize]=0; + for(i=1;i<256;i++) if(buckets[i]==buckets[i-1]+1) I[buckets[i]]=-1; + I[0]=-1; + + for(h=1;I[0]!=-(oldsize+1);h+=h) { + len=0; + for(i=0;i<oldsize+1;) { + if(I[i]<0) { + len-=I[i]; + i-=I[i]; + } else { + if(len) I[i-len]=-len; + len=V[I[i]]+1-i; + split(I,V,i,len,h); + i+=len; + len=0; + }; + }; + if(len) I[i-len]=-len; + }; + + for(i=0;i<oldsize+1;i++) I[V[i]]=i; +} + +static int +matchlen(const unsigned char *old,int oldsize,const unsigned char *newbuf,int newsize) +{ + int i; + + for(i=0;(i<oldsize)&&(i<newsize);i++) + if(old[i]!=newbuf[i]) break; + + return i; +} + +static int +search(int *I,const unsigned char *old,int oldsize, + const unsigned char *newbuf,int newsize,int st,int en,int *pos) +{ + int x,y; + + if(en-st<2) { + x=matchlen(old+I[st],oldsize-I[st],newbuf,newsize); + y=matchlen(old+I[en],oldsize-I[en],newbuf,newsize); + + if(x>y) { + *pos=I[st]; + return x; + } else { + *pos=I[en]; + return y; + } + } + + x=st+(en-st)/2; + if(memcmp(old+I[x],newbuf,std::min(oldsize-I[x],newsize))<0) { + return search(I,old,oldsize,newbuf,newsize,x,en,pos); + } else { + return search(I,old,oldsize,newbuf,newsize,st,x,pos); + } +} + +// End of 'verbatim' code. +// ------------------------------------------------------------------------ + +static void WriteHeader(SinkStream* stream, MBSPatchHeader* header) { + stream->Write(header->tag, sizeof(header->tag)); + stream->WriteVarint32(header->slen); + stream->WriteVarint32(header->scrc32); + stream->WriteVarint32(header->dlen); + stream->WriteVarint32(header->cblen); + stream->WriteVarint32(header->difflen); + stream->WriteVarint32(header->extralen); +} + +BSDiffStatus CreateBinaryPatch(SourceStream* old_stream, + SourceStream* new_stream, + SinkStream* patch_stream) +{ + base::Time start_bsdiff_time = base::Time::Now(); + LOG(INFO) << "Start bsdiff"; + size_t initial_patch_stream_length = patch_stream->Length(); + + const uint8* old = old_stream->Buffer(); + const int oldsize = old_stream->Remaining(); + + scoped_array<int> I(new(std::nothrow) int[oldsize + 1]); + scoped_array<int> V(new(std::nothrow) int[oldsize + 1]); + if (I == NULL || V == NULL) + return MEM_ERROR; + + base::Time q_start_time = base::Time::Now(); + qsufsort(I.get(), V.get(), old, oldsize); + LOG(INFO) << " done qsufsort " + << (base::Time::Now() - q_start_time).InSecondsF(); + V.reset(); + + const uint8* newbuf = new_stream->Buffer(); + const int newsize = new_stream->Remaining(); + + // Allocate newsize+1 bytes instead of newsize bytes to ensure that we never + // try to malloc(0) and get a NULL pointer. + + scoped_array<uint8> diff_bytes_array(new(std::nothrow) uint8[newsize + 1]); + scoped_array<uint8> extra_bytes_array(new(std::nothrow) uint8[newsize + 1]); + if (diff_bytes_array == NULL || extra_bytes_array == NULL) + return MEM_ERROR; + + uint8* diff_bytes = diff_bytes_array.get(); + uint8* extra_bytes = extra_bytes_array.get(); + int control_length = 0; + int diff_bytes_length = 0; + int diff_bytes_nonzero = 0; + int extra_bytes_length = 0; + int eblen = 0; + + SinkStream control_stream; + + // The patch format is a sequence of triples <copy,extra,seek> where 'copy' is + // the number of bytes to copy from the old file (possibly with mistakes), + // 'extra' is the number of bytes to copy from a stream of fresh bytes, and + // 'seek' is an offset to move to the position to copy for the next triple. + // + // The invariant at the top of this loop is that we are committed to emitting + // a triple for the part of |newbuf| surrounding a 'seed' match near + // |lastscan|. We are searching for a second match that will be the 'seed' of + // the next triple. As we scan through |newbuf|, one of four things can + // happen at the current position |scan|: + // + // 1. We find a nice match that appears to be consistent with the current + // seed. Continue scanning. It is likely that this match will become + // part of the 'copy'. + // + // 2. We find match which does much better than extending the current seed + // old match. Emit a triple for the current seed and take this match as + // the new seed for a new triple. By 'much better' we remove 8 mismatched + // bytes by taking the new seed. + // + // 3. There is not a good match. Continue scanning. These bytes will likely + // become part of the 'extra'. + // + // 4. There is no match because we reached the end of the input, |newbuf|. + + // This is how the loop advances through the bytes of |newbuf|: + // + // ...012345678901234567890123456789... + // ssssssssss Seed at |lastscan| + // xxyyyxxyyxy |scan| forward, cases (3)(x) & (1)(y) + // mmmmmmmm New match will start new seed case (2). + // fffffffffffffff |lenf| = scan forward from |lastscan| + // bbbb |lenb| = scan back from new seed |scan|. + // ddddddddddddddd Emit diff bytes for the 'copy'. + // xx Emit extra bytes. + // ssssssssssss |lastscan = scan - lenb| is new seed. + // x Cases (1) and (3) .... + + + int lastscan = 0, lastpos = 0, lastoffset = 0; + + int scan = 0; + int match_length = 0; + + while (scan < newsize) { + int pos = 0; + int oldscore = 0; // Count of how many bytes of the current match at |scan| + // extend the match at |lastscan|. + + scan += match_length; + for (int scsc = scan; scan < newsize; ++scan) { + match_length = search(I.get(), old, oldsize, + newbuf + scan, newsize - scan, + 0, oldsize, &pos); + + for ( ; scsc < scan + match_length ; scsc++) + if ((scsc + lastoffset < oldsize) && + (old[scsc + lastoffset] == newbuf[scsc])) + oldscore++; + + if ((match_length == oldscore) && (match_length != 0)) + break; // Good continuing match, case (1) + if (match_length > oldscore + 8) + break; // New seed match, case (2) + + if ((scan + lastoffset < oldsize) && + (old[scan + lastoffset] == newbuf[scan])) + oldscore--; + // Case (3) continues in this loop until we fall out of the loop (4). + } + + if ((match_length != oldscore) || (scan == newsize)) { // Cases (2) and (4) + // This next chunk of code finds the boundary between the bytes to be + // copied as part of the current triple, and the bytes to be copied as + // part of the next triple. The |lastscan| match is extended forwards as + // far as possible provided doing to does not add too many mistakes. The + // |scan| match is extended backwards in a similar way. + + // Extend the current match (if any) backwards. |lenb| is the maximal + // extension for which less than half the byte positions in the extension + // are wrong. + int lenb = 0; + if (scan < newsize) { // i.e. not case (4); there is a match to extend. + int score = 0, Sb = 0; + for (int i = 1; (scan >= lastscan + i) && (pos >= i); i++) { + if (old[pos - i] == newbuf[scan - i]) score++; + if (score*2 - i > Sb*2 - lenb) { Sb = score; lenb = i; } + } + } + + // Extend the lastscan match forward; |lenf| is the maximal extension for + // which less than half of the byte positions in entire lastscan match are + // wrong. There is a subtle point here: |lastscan| points to before the + // seed match by |lenb| bytes from the previous iteration. This is why + // the loop measures the total number of mistakes in the the match, not + // just the from the match. + int lenf = 0; + { + int score = 0, Sf = 0; + for (int i = 0; (lastscan + i < scan) && (lastpos + i < oldsize); ) { + if (old[lastpos + i] == newbuf[lastscan + i]) score++; + i++; + if (score*2 - i > Sf*2 - lenf) { Sf = score; lenf = i; } + } + } + + // If the extended scans overlap, pick a position in the overlap region + // that maximizes the exact matching bytes. + if (lastscan + lenf > scan - lenb) { + int overlap = (lastscan + lenf) - (scan - lenb); + int score = 0; + int Ss = 0, lens = 0; + for (int i = 0; i < overlap; i++) { + if (newbuf[lastscan + lenf - overlap + i] == + old[lastpos + lenf - overlap + i]) score++; + if (newbuf[scan - lenb + i] == old[pos - lenb + i]) score--; + if (score > Ss) { Ss = score; lens = i + 1; } + } + + lenf += lens - overlap; + lenb -= lens; + }; + + for (int i = 0; i < lenf; i++) { + uint8 diff_byte = newbuf[lastscan + i] - old[lastpos + i]; + diff_bytes[diff_bytes_length + i] = diff_byte; + if (diff_byte) + ++diff_bytes_nonzero; + } + int gap = (scan - lenb) - (lastscan + lenf); + for (int i = 0; i < gap; i++) + extra_bytes[extra_bytes_length + i] = newbuf[lastscan + lenf + i]; + + diff_bytes_length += lenf; + extra_bytes_length += gap; + + uint32 copy_count = lenf; + uint32 extra_count = gap; + int32 seek_adjustment = ((pos - lenb) - (lastpos + lenf)); + + control_stream.WriteVarint32(copy_count); + control_stream.WriteVarint32(extra_count); + control_stream.WriteVarint32Signed(seek_adjustment); + ++control_length; +#ifdef DEBUG_bsmedberg + LOG(INFO) << StringPrintf( + "Writing a block: copy: %-8u extra: %-8u seek: %+-9d", + copy_count, extra_count, seek_adjustment); +#endif + + lastscan = scan - lenb; // Include the backward extension in seed. + lastpos = pos - lenb; // ditto. + lastoffset = lastpos - lastscan; + } + } + + I.reset(); + + MBSPatchHeader header; + // The string will have a null terminator that we don't use, hence '-1'. + COMPILE_ASSERT(sizeof(MBS_PATCH_HEADER_TAG) - 1 == sizeof(header.tag), + MBS_PATCH_HEADER_TAG_must_match_header_field_size); + memcpy(header.tag, MBS_PATCH_HEADER_TAG, sizeof(header.tag)); + header.slen = oldsize; + header.scrc32 = CalculateCrc(old, oldsize); + header.dlen = newsize; + header.cblen = control_stream.Length(); + header.difflen = diff_bytes_length; + header.extralen = extra_bytes_length; + + WriteHeader(patch_stream, &header); + + patch_stream->Append(&control_stream); + patch_stream->Write(diff_bytes, diff_bytes_length); + patch_stream->Write(extra_bytes, extra_bytes_length); + + LOG(INFO) << "Control tuples: " << control_length + << " copy bytes: " << diff_bytes_length + << " mistakes: " << diff_bytes_nonzero + << " extra bytes: " << extra_bytes_length; + + LOG(INFO) << "Uncompressed bsdiff patch size " + << patch_stream->Length() - initial_patch_stream_length; + + LOG(INFO) << "End bsdiff " + << (base::Time::Now() - start_bsdiff_time).InSecondsF(); + + return OK; +} + +} // namespace diff --git a/third_party/courgette/bsdiff_memory_unittest.cc b/third_party/courgette/bsdiff_memory_unittest.cc new file mode 100644 index 0000000..e1add46 --- /dev/null +++ b/third_party/courgette/bsdiff_memory_unittest.cc @@ -0,0 +1,112 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "third_party/courgette/bsdiff.h"
+
+#include <string>
+
+#include "base/file_util.h"
+#include "base/path_service.h"
+#include "base/string_util.h"
+
+#include "third_party/courgette/courgette.h"
+#include "third_party/courgette/streams.h"
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+class BSDiffMemoryTest : public testing::Test {
+ public:
+ std::string FileContents(const char *file_name) const;
+ void GenerateAndTestPatch(const std::string& a, const std::string& b) const;
+
+ private:
+ void SetUp() {
+ PathService::Get(base::DIR_SOURCE_ROOT, &test_dir_);
+ // file_util::AppendToPath(&test_dir_, L"third_party");
+ file_util::AppendToPath(&test_dir_, L"courgette");
+ file_util::AppendToPath(&test_dir_, L"testdata");
+ }
+
+ std::wstring test_dir_;
+};
+
+// Reads a test file into a string.
+std::string BSDiffMemoryTest::FileContents(const char *file_name) const {
+ std::wstring file_path = test_dir_;
+ file_util::AppendToPath(&file_path, UTF8ToWide(file_name));
+ std::string file_bytes;
+ if (!file_util::ReadFileToString(file_path, &file_bytes)) {
+ EXPECT_TRUE(!"Could not read test data");
+ }
+ return file_bytes;
+}
+
+void BSDiffMemoryTest::GenerateAndTestPatch(const std::string& old_text,
+ const std::string& new_text) const {
+ courgette::SourceStream old1;
+ courgette::SourceStream new1;
+ old1.Init(old_text.c_str(), old_text.length());
+ new1.Init(new_text.c_str(), new_text.length());
+
+ courgette::SinkStream patch1;
+ courgette::BSDiffStatus status = CreateBinaryPatch(&old1, &new1, &patch1);
+ EXPECT_EQ(courgette::OK, status);
+
+ courgette::SourceStream old2;
+ courgette::SourceStream patch2;
+ old2.Init(old_text.c_str(), old_text.length());
+ patch2.Init(patch1);
+
+ courgette::SinkStream new2;
+ status = ApplyBinaryPatch(&old2, &patch2, &new2);
+ EXPECT_EQ(courgette::OK, status);
+ EXPECT_EQ(new_text.length(), new2.Length());
+ EXPECT_EQ(0, memcmp(new_text.c_str(), new2.Buffer(), new_text.length()));
+}
+
+TEST_F(BSDiffMemoryTest, TestEmpty) {
+ GenerateAndTestPatch("", "");
+}
+
+TEST_F(BSDiffMemoryTest, TestEmptyVsNonempty) {
+ GenerateAndTestPatch("", "xxx");
+}
+
+TEST_F(BSDiffMemoryTest, TestNonemptyVsEmpty) {
+ GenerateAndTestPatch("xxx", "");
+}
+
+TEST_F(BSDiffMemoryTest, TestSmallInputsWithSmallChanges) {
+ std::string file1 =
+ "I would not, could not, in a box.\n"
+ "I could not, would not, with a fox.\n"
+ "I will not eat them with a mouse.\n"
+ "I will not eat them in a house.\n"
+ "I will not eat them here or there.\n"
+ "I will not eat them anywhere.\n"
+ "I do not eat green eggs and ham.\n"
+ "I do not like them, Sam-I-am.\n";
+ std::string file2 =
+ "I would not, could not, in a BOX.\n"
+ "I could not, would not, with a FOX.\n"
+ "I will not eat them with a MOUSE.\n"
+ "I will not eat them in a HOUSE.\n"
+ "I will not eat them in a HOUSE.\n" // Extra line.
+ "I will not eat them here or THERE.\n"
+ "I will not eat them ANYWHERE.\n"
+ "I do not eat green eggs and HAM.\n"
+ "I do not like them, Sam-I-am.\n";
+ GenerateAndTestPatch(file1, file2);
+}
+
+TEST_F(BSDiffMemoryTest, TestIndenticalDlls) {
+ std::string file1 = FileContents("en-US.dll");
+ GenerateAndTestPatch(file1, file1);
+}
+
+TEST_F(BSDiffMemoryTest, TestDifferentExes) {
+ std::string file1 = FileContents("setup1.exe");
+ std::string file2 = FileContents("setup2.exe");
+ GenerateAndTestPatch(file1, file2);
+}
diff --git a/third_party/courgette/courgette.gyp b/third_party/courgette/courgette.gyp new file mode 100644 index 0000000..e0536d8 --- /dev/null +++ b/third_party/courgette/courgette.gyp @@ -0,0 +1,120 @@ +# Copyright (c) 2009 The Chromium Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+{
+ 'variables': {
+ 'chromium_code': 1,
+ },
+ 'includes': [
+ '../../build/common.gypi',
+ ],
+ 'targets': [
+ {
+ 'target_name': 'courgette_lib',
+ 'type': '<(library)',
+ 'dependencies': [
+ '../../base/base.gyp:base',
+ #'../../third_party/lzma_sdk/7z_C.vcproj',
+ ],
+ 'msvs_guid': '9A72A362-E617-4205-B9F2-43C6FB280FA1',
+ 'sources': [
+ 'adjustment_method.cc',
+ 'adjustment_method.h',
+ 'assembly_program.cc',
+ 'assembly_program.h',
+ 'bsdiff.h',
+ 'bsdiff_apply.cc',
+ 'bsdiff_create.cc',
+ 'courgette.h',
+ 'crc.cc',
+ 'crc.h',
+ 'difference_estimator.cc',
+ 'difference_estimator.h',
+ 'disassembler.cc',
+ 'disassembler.h',
+ 'encoded_program.cc',
+ 'encoded_program.h',
+ 'ensemble.cc',
+ 'ensemble.h',
+ 'ensemble_apply.cc',
+ 'ensemble_create.cc',
+ 'image_info.cc',
+ 'image_info.h',
+ 'region.h',
+ 'simple_delta.cc',
+ 'simple_delta.h',
+ 'streams.cc',
+ 'streams.h',
+ 'win32_x86_generator.h',
+ 'win32_x86_patcher.h',
+ ],
+ 'include_dirs': [
+ #'..',
+ ],
+ 'direct_dependent_settings': {
+ 'include_dirs': [
+ # '..',
+ ],
+ },
+ },
+ {
+ 'target_name': 'courgette_tool',
+ 'type': 'executable',
+ 'msvs_guid': '4EA8CE12-9C6F-45E5-9D08-720383FE3685',
+ 'sources': [
+ 'courgette_tool.cc',
+ #'memory_monitor.cc',
+ ],
+ 'dependencies': [
+ 'courgette_lib',
+ '../../base/base.gyp:base',
+ ],
+ },
+ {
+ 'target_name': 'courgette_minimal_tool',
+ 'type': 'executable',
+ 'msvs_guid': 'EB79415F-2F17-4BDC-AADD-4CA4C2D21B73',
+ 'sources': [
+ 'courgette_minimal_tool.cc',
+ ],
+ 'dependencies': [
+ 'courgette_lib',
+ '../../base/base.gyp:base',
+ ],
+ },
+ {
+ 'target_name': 'courgette_unittests',
+ 'type': 'executable',
+ 'msvs_guid': '24309F1A-4035-46F9-A3D8-F47DC4BCC2B8',
+ 'sources': [
+ 'adjustment_method_unittest.cc',
+ 'bsdiff_memory_unittest.cc',
+ 'difference_estimator_unittest.cc',
+ 'encoded_program_unittest.cc',
+ 'encode_decode_unittest.cc',
+ 'image_info_unittest.cc',
+ 'run_all_unittests.cc',
+ 'streams_unittest.cc',
+ ],
+ 'dependencies': [
+ 'courgette_lib',
+ '../../base/base.gyp:base',
+ '../../testing/gtest.gyp:gtest',
+ ],
+ },
+ {
+ 'target_name': 'courgette_fuzz',
+ 'type': 'executable',
+ 'msvs_guid': '57C27529-8CA9-4FC3-9C02-DA05B172F785',
+ 'sources': [
+ 'encoded_program_fuzz_unittest.cc',
+ ],
+ 'dependencies': [
+ 'courgette_lib',
+ '../../base/base.gyp:base',
+ '../../testing/gtest.gyp:gtest',
+ ],
+ },
+ ],
+}
diff --git a/third_party/courgette/courgette.h b/third_party/courgette/courgette.h new file mode 100644 index 0000000..09bb375 --- /dev/null +++ b/third_party/courgette/courgette.h @@ -0,0 +1,118 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef COURGETTE_COURGETTE_H_
+#define COURGETTE_COURGETTE_H_
+
+namespace courgette {
+
+// Status codes for Courgette APIs.
+//
+// Client code should only rely on the distintion between C_OK and the other
+// status codes.
+//
+enum Status {
+ C_OK = 1, // Successful operation.
+
+ C_GENERAL_ERROR = 2, // Error other than listed below.
+
+ C_READ_OPEN_ERROR = 3, // Could not open input file for reading.
+ C_READ_ERROR = 4, // Could not read from opened input file.
+
+ C_WRITE_OPEN_ERROR = 3, // Could not open output file for writing.
+ C_WRITE_ERROR = 4, // Could not write to opened output file.
+
+ C_BAD_ENSEMBLE_MAGIC = 5, // Ensemble patch has bad magic.
+ C_BAD_ENSEMBLE_VERSION = 6, // Ensemble patch has wrong version.
+ C_BAD_ENSEMBLE_HEADER = 7, // Ensemble patch has corrupt header.
+ C_BAD_ENSEMBLE_CRC = 8, // Ensemble patch has corrupt header.
+
+ C_BAD_TRANSFORM = 12, // Transform mis-specified.
+ C_BAD_BASE = 13, // Base for transform malformed.
+
+ C_BINARY_DIFF_CRC_ERROR = 14, // Internal diff input doesn't have expected
+ // CRC.
+
+ // Internal errors.
+ C_STREAM_ERROR = 20, // Unexpected error from streams.h.
+ C_STREAM_NOT_CONSUMED = 21, // Stream has extra data, is expected to be
+ // used up.
+ C_SERIALIZATION_FAILED = 22, //
+ C_DESERIALIZATION_FAILED = 23, //
+ C_INPUT_NOT_RECOGNIZED = 24, // Unrecognized input (not an executable).
+ C_DISASSEMBLY_FAILED = 25, //
+ C_ASSEMBLY_FAILED = 26, //
+ C_ADJUSTMENT_FAILED = 27, //
+
+
+};
+
+class SinkStream;
+class SinkStreamSet;
+class SourceStream;
+class SourceStreamSet;
+
+class AssemblyProgram;
+class EncodedProgram;
+
+// Applies the patch to the bytes in |old| and writes the transformed ensemble
+// to |output|.
+// Returns C_OK unless something went wrong.
+Status ApplyEnsemblePatch(SourceStream* old, SourceStream* patch,
+ SinkStream* output);
+
+// Applies the patch in |patch_file_name| to the bytes in |old_file_name| and
+// writes the transformed ensemble to |new_file_name|.
+// Returns C_OK unless something went wrong.
+// This function first validates that the patch file has a proper header, so the
+// function can be used to 'try' a patch.
+Status ApplyEnsemblePatch(const wchar_t* old_file_name,
+ const wchar_t* patch_file_name,
+ const wchar_t* new_file_name);
+
+// Generates a patch that will transform the bytes in |old| into the bytes in
+// |target|.
+// Returns C_OK unless something when wrong (unexpected).
+Status GenerateEnsemblePatch(SourceStream* old, SourceStream* target,
+ SinkStream* patch);
+
+// Parses a Windows 32-bit 'Portable Executable' format file from memory,
+// storing the pointer to the AssemblyProgram in |*output|.
+// Returns C_OK if successful, otherwise returns an error status and sets
+// |*output| to NULL.
+Status ParseWin32X86PE(const void* buffer, size_t length,
+ AssemblyProgram** output);
+
+// Converts |program| into encoded form, returning it as |*output|.
+// Returns C_OK if succeeded, otherwise returns an error status and
+// sets |*output| to NULL
+Status Encode(AssemblyProgram* program, EncodedProgram** output);
+
+
+// Serializes |encoded| into the stream set.
+// Returns C_OK if succeeded, otherwise returns an error status.
+Status WriteEncodedProgram(EncodedProgram* encoded, SinkStreamSet* sink);
+
+// Assembles |encoded|, emitting the bytes into |buffer|.
+// Returns C_OK if succeeded, otherwise returns an error status and leaves
+// |buffer| in an undefined state.
+Status Assemble(EncodedProgram* encoded, SinkStream* buffer);
+
+// Deserializes program from the stream set.
+// Returns C_OK if succeeded, otherwise returns an error status and
+// sets |*output| to NULL
+Status ReadEncodedProgram(SourceStreamSet* source, EncodedProgram** output);
+
+// Used to free an AssemblyProgram returned by other APIs.
+void DeleteAssemblyProgram(AssemblyProgram* program);
+
+// Used to free an EncodedProgram returned by other APIs.
+void DeleteEncodedProgram(EncodedProgram* encoded);
+
+// Adjusts |program| to look more like |model|.
+//
+Status Adjust(const AssemblyProgram& model, AssemblyProgram *program);
+
+} // namespace courgette
+#endif // COURGETTE_COURGETTE_H_
diff --git a/third_party/courgette/courgette_minimal_tool.cc b/third_party/courgette/courgette_minimal_tool.cc new file mode 100644 index 0000000..de5cd9e --- /dev/null +++ b/third_party/courgette/courgette_minimal_tool.cc @@ -0,0 +1,50 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// 'courgette_minimal_tool' is not meant to be a serious command-line tool. It
+// has the minimum logic to apply a Courgette patch to a file. The main purpose
+// is to monitor the code size of the patcher.
+
+#include <string>
+
+#include "base/file_util.h"
+
+#include "third_party/courgette/bsdiff.h"
+#include "third_party/courgette/courgette.h"
+#include "third_party/courgette/streams.h"
+
+void PrintHelp() {
+ fprintf(stderr,
+ "Usage:\n"
+ " courgette_minimal_tool <old-file-input> <patch-file-input>"
+ " <new-file-output>\n"
+ "\n");
+}
+
+void UsageProblem(const char* message) {
+ fprintf(stderr, "%s\n", message);
+ PrintHelp();
+ exit(1);
+}
+
+void Problem(const char* message) {
+ fprintf(stderr, "%s\n", message);
+ exit(1);
+}
+
+int wmain(int argc, const wchar_t* argv[]) {
+ if (argc != 4)
+ UsageProblem("bad args");
+
+ courgette::Status status =
+ courgette::ApplyEnsemblePatch(argv[1], argv[2], argv[3]);
+
+ if (status != courgette::C_OK) {
+ if (status == courgette::C_READ_OPEN_ERROR) Problem("Can't open file.");
+ if (status == courgette::C_WRITE_OPEN_ERROR) Problem("Can't open file.");
+ if (status == courgette::C_READ_ERROR) Problem("Can't read from file.");
+ if (status == courgette::C_WRITE_ERROR) Problem("Can't write to file.");
+ Problem("patch failed.");
+ }
+}
diff --git a/third_party/courgette/courgette_tool.cc b/third_party/courgette/courgette_tool.cc new file mode 100644 index 0000000..867101a7 --- /dev/null +++ b/third_party/courgette/courgette_tool.cc @@ -0,0 +1,405 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <vector>
+#include <string>
+
+#include "base/at_exit.h"
+#include "base/basictypes.h"
+#include "base/command_line.h"
+#include "base/file_util.h"
+#include "base/logging.h"
+#include "base/string_util.h"
+
+#include "third_party/courgette/bsdiff.h"
+#include "third_party/courgette/courgette.h"
+#include "third_party/courgette/streams.h"
+
+
+void PrintHelp() {
+ fprintf(stderr,
+ "Usage:\n"
+ " courgette_tool -dis <executable_file> <binary_assembly_file>\n"
+ " courgette_tool -asm <binary_assembly_file> <executable_file>\n"
+ " courgette_tool -disadj "
+ "<executable_file> <reference> <binary_assembly_file>\n"
+ " courgette_tool -gen <v1> <v2> <patch>\n"
+ " courgette_tool -apply <v1> <patch> <v2>\n"
+ "\n");
+}
+
+void UsageProblem(const char* message) {
+ fprintf(stderr, "%s", message);
+ fprintf(stderr, "\n");
+ PrintHelp();
+ exit(1);
+}
+
+void Problem(const char* format, ...) {
+ va_list args;
+ va_start(args, format);
+ vfprintf(stderr, format, args);
+ fprintf(stderr, "\n");
+ va_end(args);
+ exit(1);
+}
+
+std::string ReadOrFail(const std::wstring& file_name, const char* kind) {
+ FilePath file_path(file_name);
+ std::string buffer;
+ if (!file_util::ReadFileToString(file_path, &buffer))
+ Problem("Can't read %s file.", kind);
+ return buffer;
+}
+
+void WriteSinkToFile(const courgette::SinkStream *sink,
+ const std::wstring& output_file) {
+ FilePath output_path(output_file);
+ int count =
+ file_util::WriteFile(output_path,
+ reinterpret_cast<const char*>(sink->Buffer()),
+ sink->Length());
+ if (count == -1)
+ Problem("Cant write output.");
+ if (count != sink->Length())
+ Problem("Incomplete write.");
+}
+
+void Disassemble(const std::wstring& input_file,
+ const std::wstring& output_file) {
+ std::string buffer = ReadOrFail(input_file, "input");
+
+ courgette::AssemblyProgram* program = NULL;
+ const courgette::Status parse_status =
+ courgette::ParseWin32X86PE(buffer.c_str(), buffer.length(), &program);
+
+ if (parse_status != courgette::C_OK)
+ Problem("Can't parse input.");
+
+ courgette::EncodedProgram* encoded = NULL;
+ const courgette::Status encode_status = Encode(program, &encoded);
+
+ courgette::DeleteAssemblyProgram(program);
+
+ if (encode_status != courgette::C_OK)
+ Problem("Can't encode program.");
+
+ courgette::SinkStreamSet sinks;
+
+ const courgette::Status write_status =
+ courgette::WriteEncodedProgram(encoded, &sinks);
+ if (write_status != courgette::C_OK)
+ Problem("Can't serialize encoded program.");
+
+ courgette::DeleteEncodedProgram(encoded);
+
+ courgette::SinkStream sink;
+ sinks.CopyTo(&sink);
+
+ WriteSinkToFile(&sink, output_file);
+}
+
+void DisassembleAndAdjust(const std::wstring& program_file,
+ const std::wstring& model_file,
+ const std::wstring& output_file) {
+ std::string program_buffer = ReadOrFail(program_file, "program");
+ std::string model_buffer = ReadOrFail(model_file, "reference");
+
+ courgette::AssemblyProgram* program = NULL;
+ const courgette::Status parse_program_status =
+ courgette::ParseWin32X86PE(program_buffer.c_str(),
+ program_buffer.length(),
+ &program);
+ if (parse_program_status != courgette::C_OK)
+ Problem("Can't parse program input.");
+
+ courgette::AssemblyProgram* model = NULL;
+ const courgette::Status parse_model_status =
+ courgette::ParseWin32X86PE(model_buffer.c_str(),
+ model_buffer.length(),
+ &model);
+ if (parse_model_status != courgette::C_OK)
+ Problem("Can't parse model input.");
+
+ const courgette::Status adjust_status = Adjust(*model, program);
+ if (adjust_status != courgette::C_OK)
+ Problem("Can't adjust program.");
+
+ courgette::EncodedProgram* encoded = NULL;
+ const courgette::Status encode_status = Encode(program, &encoded);
+
+ courgette::DeleteAssemblyProgram(program);
+
+ if (encode_status != courgette::C_OK)
+ Problem("Can't encode program.");
+
+ courgette::SinkStreamSet sinks;
+
+ const courgette::Status write_status =
+ courgette::WriteEncodedProgram(encoded, &sinks);
+ if (write_status != courgette::C_OK)
+ Problem("Can't serialize encoded program.");
+
+ courgette::DeleteEncodedProgram(encoded);
+
+ courgette::SinkStream sink;
+ sinks.CopyTo(&sink);
+
+ WriteSinkToFile(&sink, output_file);
+}
+
+// Diffs two executable files, write a set of files for the diff, one file per
+// stream of the EncodedProgram format. Each file is the bsdiff between the
+// original file's stream and the new file's stream. This is completely
+// uninteresting to users, but it is handy for seeing how much each which
+// streams are contributing to the final file size. Adjustment is optional.
+void DisassembleAdjustDiff(const std::wstring& model_file,
+ const std::wstring& program_file,
+ const std::wstring& output_file_root,
+ bool adjust) {
+ std::string model_buffer = ReadOrFail(model_file, "'old'");
+ std::string program_buffer = ReadOrFail(program_file, "'new'");
+
+ courgette::AssemblyProgram* model = NULL;
+ const courgette::Status parse_model_status =
+ courgette::ParseWin32X86PE(model_buffer.c_str(),
+ model_buffer.length(),
+ &model);
+ if (parse_model_status != courgette::C_OK)
+ Problem("Can't parse model input.");
+
+ courgette::AssemblyProgram* program = NULL;
+ const courgette::Status parse_program_status =
+ courgette::ParseWin32X86PE(program_buffer.c_str(),
+ program_buffer.length(),
+ &program);
+ if (parse_program_status != courgette::C_OK)
+ Problem("Can't parse program input.");
+
+ if (adjust) {
+ const courgette::Status adjust_status = Adjust(*model, program);
+ if (adjust_status != courgette::C_OK)
+ Problem("Can't adjust program.");
+ }
+
+ courgette::EncodedProgram* encoded_program = NULL;
+ const courgette::Status encode_program_status =
+ Encode(program, &encoded_program);
+ courgette::DeleteAssemblyProgram(program);
+ if (encode_program_status != courgette::C_OK)
+ Problem("Can't encode program.");
+
+ courgette::EncodedProgram* encoded_model = NULL;
+ const courgette::Status encode_model_status = Encode(model, &encoded_model);
+ courgette::DeleteAssemblyProgram(model);
+ if (encode_model_status != courgette::C_OK)
+ Problem("Can't encode model.");
+
+ courgette::SinkStreamSet program_sinks;
+ const courgette::Status write_program_status =
+ courgette::WriteEncodedProgram(encoded_program, &program_sinks);
+ if (write_program_status != courgette::C_OK)
+ Problem("Can't serialize encoded program.");
+ courgette::DeleteEncodedProgram(encoded_program);
+
+ courgette::SinkStreamSet model_sinks;
+ const courgette::Status write_model_status =
+ courgette::WriteEncodedProgram(encoded_model, &model_sinks);
+ if (write_model_status != courgette::C_OK)
+ Problem("Can't serialize encoded model.");
+ courgette::DeleteEncodedProgram(encoded_program);
+
+ for (int i = 0; ; ++i) {
+ courgette::SinkStream* old_stream = model_sinks.stream(i);
+ courgette::SinkStream* new_stream = program_sinks.stream(i);
+ if (old_stream == NULL && new_stream == NULL)
+ break;
+
+ courgette::SourceStream old_source;
+ courgette::SourceStream new_source;
+ old_source.Init(*old_stream);
+ new_source.Init(*new_stream);
+ courgette::SinkStream patch_stream;
+ courgette::BSDiffStatus status =
+ courgette::CreateBinaryPatch(&old_source, &new_source, &patch_stream);
+ if (status != courgette::OK) Problem("-xxx failed.");
+
+ WriteSinkToFile(&patch_stream,
+ output_file_root + L"-" + IntToWString(i));
+ }
+}
+
+void Assemble(const std::wstring& input_file,
+ const std::wstring& output_file) {
+ std::string buffer = ReadOrFail(input_file, "input");
+
+ courgette::SourceStreamSet sources;
+ if (!sources.Init(buffer.c_str(), buffer.length()))
+ Problem("Bad input file.");
+
+ courgette::EncodedProgram* encoded = NULL;
+ const courgette::Status read_status = ReadEncodedProgram(&sources, &encoded);
+ if (read_status != courgette::C_OK)
+ Problem("Bad encoded program.");
+
+ courgette::SinkStream sink;
+
+ const courgette::Status assemble_status = courgette::Assemble(encoded, &sink);
+ if (assemble_status != courgette::C_OK)
+ Problem("Can't assemble.");
+
+ WriteSinkToFile(&sink, output_file);
+}
+
+void GenerateEnsemblePatch(const std::wstring& old_file,
+ const std::wstring& new_file,
+ const std::wstring& patch_file) {
+ std::string old_buffer = ReadOrFail(old_file, "'old' input");
+ std::string new_buffer = ReadOrFail(new_file, "'new' input");
+
+ courgette::SourceStream old_stream;
+ courgette::SourceStream new_stream;
+ old_stream.Init(old_buffer);
+ new_stream.Init(new_buffer);
+
+ courgette::SinkStream patch_stream;
+ courgette::Status status =
+ courgette::GenerateEnsemblePatch(&old_stream, &new_stream, &patch_stream);
+
+ if (status != courgette::C_OK) Problem("-gen failed.");
+
+ WriteSinkToFile(&patch_stream, patch_file);
+}
+
+void ApplyEnsemblePatch(const std::wstring& old_file,
+ const std::wstring& patch_file,
+ const std::wstring& new_file) {
+ std::string old_buffer = ReadOrFail(old_file, "'old' input");
+ std::string patch_buffer = ReadOrFail(patch_file, "'patch' input");
+
+ courgette::SourceStream old_stream;
+ courgette::SourceStream patch_stream;
+ old_stream.Init(old_buffer);
+ patch_stream.Init(patch_buffer);
+ courgette::SinkStream new_stream;
+ courgette::Status status =
+ courgette::ApplyEnsemblePatch(&old_stream, &patch_stream, &new_stream);
+
+ if (status != courgette::C_OK) Problem("-apply failed.");
+
+ WriteSinkToFile(&new_stream, new_file);
+}
+
+void GenerateBSDiffPatch(const std::wstring& old_file,
+ const std::wstring& new_file,
+ const std::wstring& patch_file) {
+ std::string old_buffer = ReadOrFail(old_file, "'old' input");
+ std::string new_buffer = ReadOrFail(new_file, "'new' input");
+
+ courgette::SourceStream old_stream;
+ courgette::SourceStream new_stream;
+ old_stream.Init(old_buffer);
+ new_stream.Init(new_buffer);
+
+ courgette::SinkStream patch_stream;
+ courgette::BSDiffStatus status =
+ courgette::CreateBinaryPatch(&old_stream, &new_stream, &patch_stream);
+
+ if (status != courgette::OK) Problem("-genbsdiff failed.");
+
+ WriteSinkToFile(&patch_stream, patch_file);
+}
+
+void ApplyBSDiffPatch(const std::wstring& old_file,
+ const std::wstring& patch_file,
+ const std::wstring& new_file) {
+ std::string old_buffer = ReadOrFail(old_file, "'old' input");
+ std::string patch_buffer = ReadOrFail(patch_file, "'patch' input");
+
+ courgette::SourceStream old_stream;
+ courgette::SourceStream patch_stream;
+ old_stream.Init(old_buffer);
+ patch_stream.Init(patch_buffer);
+
+ courgette::SinkStream new_stream;
+ courgette::BSDiffStatus status =
+ courgette::ApplyBinaryPatch(&old_stream, &patch_stream, &new_stream);
+
+ if (status != courgette::OK) Problem("-applybsdiff failed.");
+
+ WriteSinkToFile(&new_stream, new_file);
+}
+
+int main(int argc, const char* argv[]) {
+ base::AtExitManager at_exit_manager;
+ CommandLine::Init(argc, argv);
+ const CommandLine& command_line = *CommandLine::ForCurrentProcess();
+
+ bool cmd_dis = command_line.HasSwitch(L"dis");
+ bool cmd_asm = command_line.HasSwitch(L"asm");
+ bool cmd_disadj = command_line.HasSwitch(L"disadj");
+ bool cmd_make_patch = command_line.HasSwitch(L"gen");
+ bool cmd_apply_patch = command_line.HasSwitch(L"apply");
+ bool cmd_make_bsdiff_patch = command_line.HasSwitch(L"genbsdiff");
+ bool cmd_apply_bsdiff_patch = command_line.HasSwitch(L"applybsdiff");
+ bool cmd_spread_1_adjusted = command_line.HasSwitch(L"gen1a");
+ bool cmd_spread_1_unadjusted = command_line.HasSwitch(L"gen1u");
+
+ std::vector<std::wstring> values = command_line.GetLooseValues();
+
+ // '-repeat=N' is for debugging. Running many iterations can reveal leaks and
+ // bugs in cleanup.
+ int repeat_count = 1;
+ std::wstring repeat_switch = command_line.GetSwitchValue(L"repeat");
+ if (!repeat_switch.empty())
+ if (!StringToInt(repeat_switch, &repeat_count))
+ repeat_count = 1;
+
+ if (cmd_dis + cmd_asm + cmd_disadj + cmd_make_patch + cmd_apply_patch +
+ cmd_make_bsdiff_patch + cmd_apply_bsdiff_patch +
+ cmd_spread_1_adjusted + cmd_spread_1_unadjusted
+ != 1)
+ UsageProblem(
+ "Must have exactly one of:\n"
+ " -asm, -dis, -disadj, -gen or -apply, -genbsdiff or -applybsdiff.");
+
+ while (repeat_count-- > 0) {
+ if (cmd_dis) {
+ if (values.size() != 2)
+ UsageProblem("-dis <executable_file> <courgette_file>");
+ Disassemble(values[0], values[1]);
+ } else if (cmd_asm) {
+ if (values.size() != 2)
+ UsageProblem("-asm <courgette_file_input> <executable_file_output>");
+ Assemble(values[0], values[1]);
+ } else if (cmd_disadj) {
+ if (values.size() != 3)
+ UsageProblem("-disadj <executable_file> <model> <courgette_file>");
+ DisassembleAndAdjust(values[0], values[1], values[2]);
+ } else if (cmd_make_patch) {
+ if (values.size() != 3)
+ UsageProblem("-gen <old_file> <new_file> <patch_file>");
+ GenerateEnsemblePatch(values[0], values[1], values[2]);
+ } else if (cmd_apply_patch) {
+ if (values.size() != 3)
+ UsageProblem("-apply <old_file> <patch_file> <new_file>");
+ ApplyEnsemblePatch(values[0], values[1], values[2]);
+ } else if (cmd_make_bsdiff_patch) {
+ if (values.size() != 3)
+ UsageProblem("-genbsdiff <old_file> <new_file> <patch_file>");
+ GenerateBSDiffPatch(values[0], values[1], values[2]);
+ } else if (cmd_apply_bsdiff_patch) {
+ if (values.size() != 3)
+ UsageProblem("-applybsdiff <old_file> <patch_file> <new_file>");
+ ApplyBSDiffPatch(values[0], values[1], values[2]);
+ } else if (cmd_spread_1_adjusted || cmd_spread_1_unadjusted) {
+ if (values.size() != 3)
+ UsageProblem("-gen1[au] <old_file> <new_file> <patch_files_root>");
+ DisassembleAdjustDiff(values[0], values[1], values[2],
+ cmd_spread_1_adjusted);
+ } else {
+ UsageProblem("No operation specified");
+ }
+ }
+}
diff --git a/third_party/courgette/crc.cc b/third_party/courgette/crc.cc new file mode 100644 index 0000000..6bf51fe --- /dev/null +++ b/third_party/courgette/crc.cc @@ -0,0 +1,22 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Calculate Crc by calling CRC method in LZMA SDK
+
+#include "third_party/courgette/crc.h"
+
+extern "C" {
+#include "third_party/lzma_sdk/7zCrc.h"
+}
+
+namespace courgette {
+
+uint32 CalculateCrc(const uint8* buffer, size_t size) {
+ // CrcGenerateTable();
+ uint32 crc = 0xffffffffL;
+ // crc = ~CrcCalc(buffer, size);
+ return crc;
+}
+
+} // namespace
diff --git a/third_party/courgette/crc.h b/third_party/courgette/crc.h new file mode 100644 index 0000000..6f4fbb0 --- /dev/null +++ b/third_party/courgette/crc.h @@ -0,0 +1,17 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef COURGETTE_CRC_H_
+#define COURGETTE_CRC_H_
+
+#include "base/basictypes.h"
+
+namespace courgette {
+
+// Calculates Crc of the given buffer by calling CRC method in LZMA SDK
+//
+uint32 CalculateCrc(const uint8* buffer, size_t size);
+
+} // namespace courgette
+#endif // COURGETTE_CRC_H_
diff --git a/third_party/courgette/difference_estimator.cc b/third_party/courgette/difference_estimator.cc new file mode 100644 index 0000000..943eafb --- /dev/null +++ b/third_party/courgette/difference_estimator.cc @@ -0,0 +1,118 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// We want to measure the similarity of two sequences of bytes as a surrogate
+// for measuring how well a second sequence will compress differentially to the
+// first sequence.
+
+#include "third_party/courgette/difference_estimator.h"
+
+#include "base/hash_tables.h"
+
+namespace courgette {
+
+// Our difference measure is the number of k-tuples that occur in Subject that
+// don't occur in Base.
+const int kTupleSize = 4;
+
+namespace {
+
+COMPILE_ASSERT(kTupleSize >= 4 && kTupleSize <= 8, kTupleSize_between_4_and_8);
+
+size_t HashTuple(const uint8* source) {
+ size_t hash1 = *reinterpret_cast<const uint32*>(source);
+ size_t hash2 = *reinterpret_cast<const uint32*>(source + kTupleSize - 4);
+ size_t hash = ((hash1 * 17 + hash2 * 37) + (hash1 >> 17)) ^ (hash2 >> 23);
+ return hash;
+}
+
+bool RegionsEqual(const Region& a, const Region& b) {
+ if (a.length() != b.length())
+ return false;
+ return memcmp(a.start(), b.start(), a.length()) == 0;
+}
+
+} // anonymous namepace
+
+class DifferenceEstimator::Base {
+ public:
+ explicit Base(const Region& region) : region_(region) { }
+
+ void Init() {
+ const uint8* start = region_.start();
+ const uint8* end = region_.end() - (kTupleSize - 1);
+ for (const uint8* p = start; p < end; ++p) {
+ size_t hash = HashTuple(p);
+ hashes_.insert(hash);
+ }
+ }
+
+ const Region& region() const { return region_; }
+
+ private:
+ Region region_;
+ base::hash_set<size_t> hashes_;
+
+ friend class DifferenceEstimator;
+ DISALLOW_COPY_AND_ASSIGN(Base);
+};
+
+class DifferenceEstimator::Subject {
+ public:
+ explicit Subject(const Region& region) : region_(region) {}
+
+ const Region& region() const { return region_; }
+
+ private:
+ Region region_;
+
+ DISALLOW_COPY_AND_ASSIGN(Subject);
+};
+
+DifferenceEstimator::DifferenceEstimator() {}
+
+DifferenceEstimator::~DifferenceEstimator() {
+ for (size_t i = 0; i < owned_bases_.size(); ++i)
+ delete owned_bases_[i];
+ for (size_t i = 0; i < owned_subjects_.size(); ++i)
+ delete owned_subjects_[i];
+}
+
+DifferenceEstimator::Base* DifferenceEstimator::MakeBase(const Region& region) {
+ Base* base = new Base(region);
+ base->Init();
+ owned_bases_.push_back(base);
+ return base;
+}
+
+DifferenceEstimator::Subject* DifferenceEstimator::MakeSubject(
+ const Region& region) {
+ Subject* subject = new Subject(region);
+ owned_subjects_.push_back(subject);
+ return subject;
+}
+
+size_t DifferenceEstimator::Measure(Base* base, Subject* subject) {
+ size_t mismatches = 0;
+ const uint8* start = subject->region().start();
+ const uint8* end = subject->region().end() - (kTupleSize - 1);
+
+ const uint8* p = start;
+ while (p < end) {
+ size_t hash = HashTuple(p);
+ if (base->hashes_.find(hash) == base->hashes_.end()) {
+ ++mismatches;
+ }
+ p += 1;
+ }
+
+ if (mismatches == 0) {
+ if (RegionsEqual(base->region(), subject->region()))
+ return 0;
+ }
+ ++mismatches; // Guarantee not zero.
+ return mismatches;
+}
+
+} // namespace
diff --git a/third_party/courgette/difference_estimator.h b/third_party/courgette/difference_estimator.h new file mode 100644 index 0000000..bd550ec --- /dev/null +++ b/third_party/courgette/difference_estimator.h @@ -0,0 +1,58 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// A DifferenceEstimator class provides a means for quickly estimating the
+// difference between two regions of memory.
+
+#ifndef COURGETTE_DIFFERENCE_ESTIMATOR_H_
+#define COURGETTE_DIFFERENCE_ESTIMATOR_H_
+
+#include <vector>
+
+#include "third_party/courgette/region.h"
+
+namespace courgette {
+
+// A DifferenceEstimator simplifies the task of determining which 'Subject' byte
+// strings (stored in regions of memory) are good matches to existing 'Base'
+// regions. The ultimate measure would be to try full differential compression
+// and measure the output size, but an estimate that correlates well with the
+// full compression is more efficient.
+//
+// The measure is asymmetric, if the Subject is a small substring of the Base
+// then it should match very well.
+//
+// The comparison is staged: first make Base and Subject objects for the regions
+// and then call 'Measure' to get the estimate. The staging allows multiple
+// comparisons to be more efficient by precomputing information used in the
+// comparison.
+//
+class DifferenceEstimator {
+ public:
+ DifferenceEstimator();
+ ~DifferenceEstimator();
+
+ class Base;
+ class Subject;
+
+ // This DifferenceEstimator owns the objects returned by MakeBase and
+ // MakeSubject. Caller continues to own memory at |region| and must not free
+ // it until ~DifferenceEstimator has been called.
+ Base* MakeBase(const Region& region);
+ Subject* MakeSubject(const Region& region);
+
+ // Returns a value correlated with the size of the bsdiff or xdelta difference
+ // from |base| to |subject|. Returns zero iff the base and subject regions
+ // are bytewise identical.
+ size_t Measure(Base* base, Subject* subject);
+
+ private:
+ std::vector<Base*> owned_bases_;
+ std::vector<Subject*> owned_subjects_;
+ DISALLOW_COPY_AND_ASSIGN(DifferenceEstimator);
+};
+
+} // namespace
+
+#endif // COURGETTE_DIFFERENCE_ESTIMATOR_H_
diff --git a/third_party/courgette/difference_estimator_unittest.cc b/third_party/courgette/difference_estimator_unittest.cc new file mode 100644 index 0000000..6cc8afd --- /dev/null +++ b/third_party/courgette/difference_estimator_unittest.cc @@ -0,0 +1,58 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "third_party/courgette/difference_estimator.h"
+
+#include <string>
+
+#include "testing/gtest/include/gtest/gtest.h"
+#include "third_party/courgette/region.h"
+
+using courgette::DifferenceEstimator;
+using courgette::Region;
+
+TEST(DifferenceEstimatorTest, TestSame) {
+ static const char kString1[] = "Hello world";
+ // kString2 is stack allocated to prevent string sharing.
+ const char kString2[] = "Hello world";
+ DifferenceEstimator difference_estimator;
+ DifferenceEstimator::Base* base =
+ difference_estimator.MakeBase(Region(kString1, sizeof(kString1)));
+ DifferenceEstimator::Subject* subject =
+ difference_estimator.MakeSubject(Region(kString2, sizeof(kString2)));
+ EXPECT_EQ(0, difference_estimator.Measure(base, subject));
+}
+
+TEST(DifferenceEstimatorTest, TestDifferent) {
+ static const char kString1[] = "Hello world";
+ static const char kString2[] = "Hello universe";
+ DifferenceEstimator difference_estimator;
+ DifferenceEstimator::Base* base =
+ difference_estimator.MakeBase(Region(kString1, sizeof(kString1)));
+ DifferenceEstimator::Subject* subject =
+ difference_estimator.MakeSubject(Region(kString2, sizeof(kString2)));
+ EXPECT_EQ(10, difference_estimator.Measure(base, subject));
+}
+
+TEST(DifferenceEstimatorTest, TestDifferentSuperstring) {
+ static const char kString1[] = "abcdabcdabcd";
+ static const char kString2[] = "abcdabcdabcdabcd";
+ DifferenceEstimator difference_estimator;
+ DifferenceEstimator::Base* base =
+ difference_estimator.MakeBase(Region(kString1, sizeof(kString1)-1));
+ DifferenceEstimator::Subject* subject =
+ difference_estimator.MakeSubject(Region(kString2, sizeof(kString2)-1));
+ EXPECT_EQ(1, difference_estimator.Measure(base, subject));
+}
+
+TEST(DifferenceEstimatorTest, TestDifferentSubstring) {
+ static const char kString1[] = "abcdabcdabcdabcd";
+ static const char kString2[] = "abcdabcdabcd";
+ DifferenceEstimator difference_estimator;
+ DifferenceEstimator::Base* base =
+ difference_estimator.MakeBase(Region(kString1, sizeof(kString1)-1));
+ DifferenceEstimator::Subject* subject =
+ difference_estimator.MakeSubject(Region(kString2, sizeof(kString2)-1));
+ EXPECT_EQ(1, difference_estimator.Measure(base, subject));
+}
diff --git a/third_party/courgette/disassembler.cc b/third_party/courgette/disassembler.cc new file mode 100644 index 0000000..6ebb2da --- /dev/null +++ b/third_party/courgette/disassembler.cc @@ -0,0 +1,436 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "third_party/courgette/disassembler.h"
+
+#include <algorithm>
+#include <iostream>
+#include <string>
+#include <vector>
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+
+#include "third_party/courgette/assembly_program.h"
+#include "third_party/courgette/courgette.h"
+#include "third_party/courgette/encoded_program.h"
+#include "third_party/courgette/image_info.h"
+
+// COURGETTE_HISTOGRAM_TARGETS prints out a histogram of how frequently
+// different target addresses are referenced. Purely for debugging.
+#define COURGETTE_HISTOGRAM_TARGETS 0
+
+namespace courgette {
+
+class DisassemblerWin32X86 : public Disassembler {
+ public:
+ explicit DisassemblerWin32X86(PEInfo* pe_info)
+ : pe_info_(pe_info),
+ incomplete_disassembly_(false) {
+ }
+
+ virtual bool Disassemble(AssemblyProgram* target);
+
+ virtual void Destroy() { delete this; }
+
+ protected:
+ PEInfo& pe_info() { return *pe_info_; }
+
+ void ParseFile(AssemblyProgram* target);
+ bool ParseAbs32Relocs();
+ void ParseRel32RelocsFromSections();
+ void ParseRel32RelocsFromSection(const Section* section);
+
+ void ParseNonSectionFileRegion(uint32 start_file_offset,
+ uint32 end_file_offset,
+ AssemblyProgram* program);
+ void ParseFileRegion(const Section* section,
+ uint32 start_file_offset, uint32 end_file_offset,
+ AssemblyProgram* program);
+
+#if COURGETTE_HISTOGRAM_TARGETS
+ void HistogramTargets(const char* kind, const std::map<RVA, int>& map);
+#endif
+
+ PEInfo* pe_info_;
+ bool incomplete_disassembly_; // 'true' if can leave out 'uninteresting' bits
+
+ std::vector<RVA> abs32_locations_;
+ std::vector<RVA> rel32_locations_;
+
+#if COURGETTE_HISTOGRAM_TARGETS
+ std::map<RVA, int> abs32_target_rvas_;
+ std::map<RVA, int> rel32_target_rvas_;
+#endif
+};
+
+bool DisassemblerWin32X86::Disassemble(AssemblyProgram* target) {
+ if (!pe_info().ok())
+ return false;
+
+ target->set_image_base(pe_info().image_base());
+
+ if (!ParseAbs32Relocs())
+ return false;
+
+ ParseRel32RelocsFromSections();
+
+ ParseFile(target);
+
+ target->DefaultAssignIndexes();
+ return true;
+}
+
+static uint32 Read32LittleEndian(const void* address) {
+ return *reinterpret_cast<const uint32*>(address);
+}
+
+bool DisassemblerWin32X86::ParseAbs32Relocs() {
+ abs32_locations_.clear();
+ if (!pe_info().ParseRelocs(&abs32_locations_))
+ return false;
+
+ std::sort(abs32_locations_.begin(), abs32_locations_.end());
+
+#if COURGETTE_HISTOGRAM_TARGETS
+ for (size_t i = 0; i < abs32_locations_.size(); ++i) {
+ RVA rva = abs32_locations_[i];
+ // The 4 bytes at the relocation are a reference to some address.
+ uint32 target_address = Read32LittleEndian(pe_info().RVAToPointer(rva));
+ ++abs32_target_rvas_[target_address - pe_info().image_base()];
+ }
+#endif
+ return true;
+}
+
+void DisassemblerWin32X86::ParseRel32RelocsFromSections() {
+ uint32 file_offset = 0;
+ while (file_offset < pe_info().length()) {
+ const Section* section = pe_info().FindNextSection(file_offset);
+ if (section == NULL)
+ break;
+ if (file_offset < section->file_offset_of_raw_data)
+ file_offset = section->file_offset_of_raw_data;
+ ParseRel32RelocsFromSection(section);
+ file_offset += section->size_of_raw_data;
+ }
+ std::sort(rel32_locations_.begin(), rel32_locations_.end());
+
+#if COURGETTE_HISTOGRAM_TARGETS
+ LOG(INFO) << "abs32_locations_ " << abs32_locations_.size();
+ LOG(INFO) << "rel32_locations_ " << rel32_locations_.size();
+ LOG(INFO) << "abs32_target_rvas_ " << abs32_target_rvas_.size();
+ LOG(INFO) << "rel32_target_rvas_ " << rel32_target_rvas_.size();
+
+ int common = 0;
+ std::map<RVA, int>::iterator abs32_iter = abs32_target_rvas_.begin();
+ std::map<RVA, int>::iterator rel32_iter = rel32_target_rvas_.begin();
+ while (abs32_iter != abs32_target_rvas_.end() &&
+ rel32_iter != rel32_target_rvas_.end()) {
+ if (abs32_iter->first < rel32_iter->first)
+ ++abs32_iter;
+ else if (rel32_iter->first < abs32_iter->first)
+ ++rel32_iter;
+ else {
+ ++common;
+ ++abs32_iter;
+ ++rel32_iter;
+ }
+ }
+ LOG(INFO) << "common " << common;
+#endif
+}
+
+void DisassemblerWin32X86::ParseRel32RelocsFromSection(const Section* section) {
+ // TODO(sra): use characteristic.
+ bool isCode = strcmp(section->name, ".text") == 0;
+ if (!isCode)
+ return;
+
+ uint32 start_file_offset = section->file_offset_of_raw_data;
+ uint32 end_file_offset = start_file_offset + section->size_of_raw_data;
+ RVA relocs_start_rva = pe_info().base_relocation_table().address_;
+
+ const uint8* start_pointer = pe_info().FileOffsetToPointer(start_file_offset);
+ const uint8* end_pointer = pe_info().FileOffsetToPointer(end_file_offset);
+
+ RVA start_rva = pe_info().FileOffsetToRVA(start_file_offset);
+ RVA end_rva = start_rva + section->virtual_size;
+
+ // Quick way to convert from Pointer to RVA within a single Section is to
+ // subtract 'pointer_to_rva'.
+ const uint8* const adjust_pointer_to_rva = start_pointer - start_rva;
+
+ std::vector<RVA>::iterator abs32_pos = abs32_locations_.begin();
+
+ // Find the rel32 relocations.
+ const uint8* p = start_pointer;
+ while (p < end_pointer) {
+ RVA current_rva = p - adjust_pointer_to_rva;
+ if (current_rva == relocs_start_rva) {
+ uint32 relocs_size = pe_info().base_relocation_table().size_;
+ if (relocs_size) {
+ p += relocs_size;
+ continue;
+ }
+ }
+
+ //while (abs32_pos != abs32_locations_.end() && *abs32_pos < current_rva)
+ // ++abs32_pos;
+
+ // Heuristic discovery of rel32 locations in instruction stream: are the
+ // next few bytes the start of an instruction containing a rel32
+ // addressing mode?
+ const uint8* rel32 = NULL;
+
+ if (p + 5 < end_pointer) {
+ if (*p == 0xE8 || *p == 0xE9) { // jmp rel32 and call rel32
+ rel32 = p + 1;
+ }
+ }
+ if (p + 6 < end_pointer) {
+ if (*p == 0x0F && (*(p+1) & 0xF0) == 0x80) { // Jcc long form
+ if (p[1] != 0x8A && p[1] != 0x8B) // JPE/JPO unlikely
+ rel32 = p + 2;
+ }
+ }
+ if (rel32) {
+ RVA rel32_rva = rel32 - adjust_pointer_to_rva;
+
+ // Is there an abs32 reloc overlapping the candidate?
+ while (abs32_pos != abs32_locations_.end() && *abs32_pos < rel32_rva - 3)
+ ++abs32_pos;
+ // Now: (*abs32_pos > rel32_rva - 4) i.e. the lowest addressed 4-byte
+ // region that could overlap rel32_rva.
+ if (abs32_pos != abs32_locations_.end()) {
+ if (*abs32_pos < rel32_rva + 4) {
+ // Beginning of abs32 reloc is before end of rel32 reloc so they
+ // overlap. Skip four bytes past the abs32 reloc.
+ p += (*abs32_pos + 4) - current_rva;
+ continue;
+ }
+ }
+
+ RVA target_rva = rel32_rva + 4 + Read32LittleEndian(rel32);
+ // To be valid, rel32 target must be within image, and within this
+ // section.
+ if (pe_info().IsValidRVA(target_rva) &&
+ start_rva <= target_rva && target_rva < end_rva) {
+ rel32_locations_.push_back(rel32_rva);
+#if COURGETTE_HISTOGRAM_TARGETS
+ ++rel32_target_rvas_[target_rva];
+#endif
+ p += 4;
+ continue;
+ }
+ }
+ p += 1;
+ }
+}
+
+void DisassemblerWin32X86::ParseFile(AssemblyProgram* program) {
+ // Walk all the bytes in the file, whether or not in a section.
+ uint32 file_offset = 0;
+ while (file_offset < pe_info().length()) {
+ const Section* section = pe_info().FindNextSection(file_offset);
+ if (section == NULL) {
+ // No more sections. There should not be extra stuff following last
+ // section.
+ // ParseNonSectionFileRegion(file_offset, pe_info().length(), program);
+ break;
+ }
+ if (file_offset < section->file_offset_of_raw_data) {
+ uint32 section_start_offset = section->file_offset_of_raw_data;
+ ParseNonSectionFileRegion(file_offset, section_start_offset, program);
+ file_offset = section_start_offset;
+ }
+ uint32 end = file_offset + section->size_of_raw_data;
+ ParseFileRegion(section, file_offset, end, program);
+ file_offset = end;
+ }
+
+#if COURGETTE_HISTOGRAM_TARGETS
+ HistogramTargets("abs32 relocs", abs32_target_rvas_);
+ HistogramTargets("rel32 relocs", rel32_target_rvas_);
+#endif
+}
+
+void DisassemblerWin32X86::ParseNonSectionFileRegion(
+ uint32 start_file_offset,
+ uint32 end_file_offset,
+ AssemblyProgram* program) {
+ if (incomplete_disassembly_)
+ return;
+
+ const uint8* start = pe_info().FileOffsetToPointer(start_file_offset);
+ const uint8* end = pe_info().FileOffsetToPointer(end_file_offset);
+
+ const uint8* p = start;
+
+ while (p < end) {
+ program->EmitByteInstruction(*p);
+ ++p;
+ }
+}
+
+void DisassemblerWin32X86::ParseFileRegion(
+ const Section* section,
+ uint32 start_file_offset, uint32 end_file_offset,
+ AssemblyProgram* program) {
+ RVA relocs_start_rva = pe_info().base_relocation_table().address_;
+
+ const uint8* start_pointer = pe_info().FileOffsetToPointer(start_file_offset);
+ const uint8* end_pointer = pe_info().FileOffsetToPointer(end_file_offset);
+
+ RVA start_rva = pe_info().FileOffsetToRVA(start_file_offset);
+ RVA end_rva = start_rva + section->virtual_size;
+
+ // Quick way to convert from Pointer to RVA within a single Section is to
+ // subtract 'pointer_to_rva'.
+ const uint8* const adjust_pointer_to_rva = start_pointer - start_rva;
+
+ std::vector<RVA>::iterator rel32_pos = rel32_locations_.begin();
+ std::vector<RVA>::iterator abs32_pos = abs32_locations_.begin();
+
+ program->EmitOriginInstruction(start_rva);
+
+ const uint8* p = start_pointer;
+
+ while (p < end_pointer) {
+ RVA current_rva = p - adjust_pointer_to_rva;
+
+ // The base relocation table is usually in the .relocs section, but it could
+ // actually be anywhere. Make sure we skip it because we will regenerate it
+ // during assembly.
+ if (current_rva == relocs_start_rva) {
+ program->EmitMakeRelocsInstruction();
+ uint32 relocs_size = pe_info().base_relocation_table().size_;
+ if (relocs_size) {
+ p += relocs_size;
+ continue;
+ }
+ }
+
+ while (abs32_pos != abs32_locations_.end() && *abs32_pos < current_rva)
+ ++abs32_pos;
+
+ if (abs32_pos != abs32_locations_.end() && *abs32_pos == current_rva) {
+ uint32 target_address = Read32LittleEndian(p);
+ RVA target_rva = target_address - pe_info().image_base();
+ // TODO(sra): target could be Label+offset. It is not clear how to guess
+ // which it might be. We assume offset==0.
+ program->EmitAbs32(program->FindOrMakeAbs32Label(target_rva));
+ p += 4;
+ continue;
+ }
+
+ while (rel32_pos != rel32_locations_.end() && *rel32_pos < current_rva)
+ ++rel32_pos;
+
+ if (rel32_pos != rel32_locations_.end() && *rel32_pos == current_rva) {
+ RVA target_rva = current_rva + 4 + Read32LittleEndian(p);
+ program->EmitRel32(program->FindOrMakeRel32Label(target_rva));
+ p += 4;
+ continue;
+ }
+
+ if (incomplete_disassembly_) {
+ if ((abs32_pos == abs32_locations_.end() || end_rva <= *abs32_pos) &&
+ (rel32_pos == rel32_locations_.end() || end_rva <= *rel32_pos) &&
+ (end_rva <= relocs_start_rva || current_rva >= relocs_start_rva)) {
+ // No more relocs in this section, don't bother encoding bytes.
+ break;
+ }
+ }
+
+ program->EmitByteInstruction(*p);
+ p += 1;
+ }
+}
+
+#if COURGETTE_HISTOGRAM_TARGETS
+// Histogram is printed to std::cout. It is purely for debugging the algorithm
+// and is only enabled manually in 'exploration' builds. I don't want to add
+// command-line configuration for this feature because this code has to be
+// small, which means compiled-out.
+void DisassemblerWin32X86::HistogramTargets(const char* kind,
+ const std::map<RVA, int>& map) {
+ int total = 0;
+ std::map<int, std::vector<RVA> > h;
+ for (std::map<RVA, int>::const_iterator p = map.begin();
+ p != map.end();
+ ++p) {
+ h[p->second].push_back(p->first);
+ total += p->second;
+ }
+
+ std::cout << total << " " << kind << " to "
+ << map.size() << " unique targets" << std::endl;
+
+ std::cout << "indegree: #targets-with-indegree (example)" << std::endl;
+ const int kFirstN = 15;
+ bool someSkipped = false;
+ int index = 0;
+ for (std::map<int, std::vector<RVA> >::reverse_iterator p = h.rbegin();
+ p != h.rend();
+ ++p) {
+ ++index;
+ if (index <= kFirstN || p->first <= 3) {
+ if (someSkipped) {
+ std::cout << "..." << std::endl;
+ }
+ size_t count = p->second.size();
+ std::cout << std::dec << p->first << ": " << count;
+ if (count <= 2) {
+ for (size_t i = 0; i < count; ++i)
+ std::cout << " " << pe_info().DescribeRVA(p->second[i]);
+ }
+ std::cout << std::endl;
+ someSkipped = false;
+ } else {
+ someSkipped = true;
+ }
+ }
+}
+#endif // COURGETTE_HISTOGRAM_TARGETS
+
+Disassembler* Disassembler::MakeDisassemberWin32X86(PEInfo* pe_info) {
+ return new DisassemblerWin32X86(pe_info);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+Status ParseWin32X86PE(const void* buffer, size_t length,
+ AssemblyProgram** output) {
+ *output = NULL;
+
+ PEInfo* pe_info = new PEInfo();
+ pe_info->Init(buffer, length);
+
+ if (!pe_info->ParseHeader()) {
+ delete pe_info;
+ return C_INPUT_NOT_RECOGNIZED;
+ }
+
+ Disassembler* disassembler = Disassembler::MakeDisassemberWin32X86(pe_info);
+ AssemblyProgram* program = new AssemblyProgram();
+
+ if (!disassembler->Disassemble(program)) {
+ delete program;
+ disassembler->Destroy();
+ delete pe_info;
+ return C_DISASSEMBLY_FAILED;
+ }
+
+ disassembler->Destroy();
+ delete pe_info;
+ *output = program;
+ return C_OK;
+}
+
+void DeleteAssemblyProgram(AssemblyProgram* program) {
+ delete program;
+}
+
+} // namespace courgette
diff --git a/third_party/courgette/disassembler.h b/third_party/courgette/disassembler.h new file mode 100644 index 0000000..595412e --- /dev/null +++ b/third_party/courgette/disassembler.h @@ -0,0 +1,39 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef COURGETTE_DISASSEMBLER_H_
+#define COURGETTE_DISASSEMBLER_H_
+
+#include "base/basictypes.h"
+
+namespace courgette {
+
+class AssemblyProgram;
+class PEInfo;
+
+class Disassembler {
+ public:
+ // Factory methods for making disassemblers for various kinds of executables.
+ // We have only one so far.
+
+ static Disassembler* MakeDisassemberWin32X86(PEInfo* pe_info);
+
+ // Disassembles the item passed to the factory method into the output
+ // parameter 'program'.
+ virtual bool Disassemble(AssemblyProgram* program) = 0;
+
+ // Deletes 'this' disassembler.
+ virtual void Destroy() = 0;
+
+ protected:
+ Disassembler() {}
+ virtual ~Disassembler() {}
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(Disassembler);
+};
+
+} // namespace courgette
+#endif // COURGETTE_DISASSEMBLER_H_
+
diff --git a/third_party/courgette/encode_decode_unittest.cc b/third_party/courgette/encode_decode_unittest.cc new file mode 100644 index 0000000..25a3913 --- /dev/null +++ b/third_party/courgette/encode_decode_unittest.cc @@ -0,0 +1,106 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include <string> + +#include "base/path_service.h" +#include "base/file_util.h" +#include "base/string_util.h" + +#include "third_party/courgette/courgette.h" +#include "third_party/courgette/streams.h" + +#include "testing/gtest/include/gtest/gtest.h" + +class EncodeDecodeTest : public testing::Test { + public: + void TestExe(const char *) const; + + private: + void SetUp() { + PathService::Get(base::DIR_SOURCE_ROOT, &testdata_dir_); + // file_util::AppendToPath(&testdata_dir_, L"third_party"); + file_util::AppendToPath(&testdata_dir_, L"courgette"); + file_util::AppendToPath(&testdata_dir_, L"testdata"); + } + + void TearDown() { } + + // Returns contents of |file_name| as uninterprested bytes stored in a string. + std::string FileContents(const char* file_name) const; + + std::wstring testdata_dir_; // Full path name of testdata directory +}; + +// Reads a test file into a string. +std::string EncodeDecodeTest::FileContents(const char* file_name) const { + std::wstring file_path = testdata_dir_; + file_util::AppendToPath(&file_path, UTF8ToWide(file_name)); + std::string file_contents; + if (!file_util::ReadFileToString(file_path, &file_contents)) { + EXPECT_TRUE(!"Could not read test data"); + } + return file_contents; +} + +void EncodeDecodeTest::TestExe(const char* file_name) const { + // Test top-level Courgette API for converting an a file to a binary + // assembly representation and back. + std::string file1 = FileContents(file_name); + + const void* original_buffer = file1.c_str(); + size_t original_length = file1.size(); + + courgette::AssemblyProgram* program = NULL; + const courgette::Status parse_status = + courgette::ParseWin32X86PE(original_buffer, original_length, &program); + EXPECT_EQ(courgette::C_OK, parse_status); + + courgette::EncodedProgram* encoded = NULL; + + const courgette::Status encode_status = Encode(program, &encoded); + EXPECT_EQ(courgette::C_OK, encode_status); + + DeleteAssemblyProgram(program); + + courgette::SinkStreamSet sinks; + const courgette::Status write_status = WriteEncodedProgram(encoded, &sinks); + EXPECT_EQ(courgette::C_OK, write_status); + + DeleteEncodedProgram(encoded); + + courgette::SinkStream sink; + bool can_collect = sinks.CopyTo(&sink); + EXPECT_TRUE(can_collect); + + const void* buffer = sink.Buffer(); + size_t length = sink.Length(); + + EXPECT_EQ(971850, length); + + courgette::SourceStreamSet sources; + bool can_get_source_streams = sources.Init(buffer, length); + EXPECT_TRUE(can_get_source_streams); + + courgette::EncodedProgram *encoded2 = NULL; + const courgette::Status read_status = ReadEncodedProgram(&sources, &encoded2); + EXPECT_EQ(courgette::C_OK, read_status); + + courgette::SinkStream assembled; + const courgette::Status assemble_status = Assemble(encoded2, &assembled); + EXPECT_EQ(courgette::C_OK, assemble_status); + + const void* assembled_buffer = assembled.Buffer(); + size_t assembled_length = assembled.Length(); + + EXPECT_EQ(original_length, assembled_length); + EXPECT_EQ(0, memcmp(original_buffer, assembled_buffer, original_length)); + + DeleteEncodedProgram(encoded2); +} + + +TEST_F(EncodeDecodeTest, All) { + TestExe("setup1.exe"); +} diff --git a/third_party/courgette/encoded_program.cc b/third_party/courgette/encoded_program.cc new file mode 100644 index 0000000..0e9f164 --- /dev/null +++ b/third_party/courgette/encoded_program.cc @@ -0,0 +1,573 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "third_party/courgette/encoded_program.h" + +#include <algorithm> +#include <map> +#include <string> +#include <vector> + +#include "base/logging.h" +#include "base/sys_info.h" + +#include "third_party/courgette/courgette.h" +#include "third_party/courgette/streams.h" + +namespace courgette { + +// Stream indexes. +const int kStreamMisc = 0; +const int kStreamOps = 1; +const int kStreamBytes = 2; +const int kStreamAbs32Indexes = 3; +const int kStreamRel32Indexes = 4; +const int kStreamAbs32Addresses = 5; +const int kStreamRel32Addresses = 6; +const int kStreamCopyCounts = 7; +const int kStreamOriginAddresses = kStreamMisc; + +const int kStreamLimit = 9; + +// Binary assembly language operations. +enum EncodedProgram::OP { + ORIGIN, // ORIGIN <rva> - set address for subsequent assembly. + COPY, // COPY <count> <bytes> - copy bytes to output. + COPY1, // COPY1 <byte> - same as COPY 1 <byte>. + REL32, // REL32 <index> - emit rel32 encoded reference to address at + // address table offset <index> + ABS32, // ABS32 <index> - emit abs32 encoded reference to address at + // address table offset <index> + MAKE_BASE_RELOCATION_TABLE, // Emit base relocation table blocks. + OP_LAST +}; + + +// Constructor is here rather than in the header. Although the constructor +// appears to do nothing it is fact quite large because of the implict calls to +// field constructors. Ditto for the destructor. +EncodedProgram::EncodedProgram() {} +EncodedProgram::~EncodedProgram() {} + +// Serializes a vector of integral values using Varint32 coding. +template<typename T> +void WriteVector(const std::vector<T>& items, SinkStream* buffer) { + size_t count = items.size(); + buffer->WriteVarint32(count); + for (size_t i = 0; i < count; ++i) { + COMPILE_ASSERT(sizeof(T) <= sizeof(uint32), T_must_fit_in_uint32); + buffer->WriteVarint32(static_cast<uint32>(items[i])); + } +} + +template<typename T> +bool ReadVector(std::vector<T>* items, SourceStream* buffer) { + uint32 count; + if (!buffer->ReadVarint32(&count)) + return false; + + items->clear(); + items->reserve(count); + for (size_t i = 0; i < count; ++i) { + uint32 item; + if (!buffer->ReadVarint32(&item)) + return false; + items->push_back(static_cast<T>(item)); + } + + return true; +} + +// Serializes a vector, using delta coding followed by Varint32 coding. +void WriteU32Delta(const std::vector<uint32>& set, SinkStream* buffer) { + size_t count = set.size(); + buffer->WriteVarint32(count); + uint32 prev = 0; + for (size_t i = 0; i < count; ++i) { + uint32 current = set[i]; + uint32 delta = current - prev; + buffer->WriteVarint32(delta); + prev = current; + } +} + +static bool ReadU32Delta(std::vector<uint32>* set, SourceStream* buffer) { + uint32 count; + + if (!buffer->ReadVarint32(&count)) + return false; + + set->clear(); + set->reserve(count); + uint32 prev = 0; + + for (size_t i = 0; i < count; ++i) { + uint32 delta; + if (!buffer->ReadVarint32(&delta)) + return false; + uint32 current = prev + delta; + set->push_back(current); + prev = current; + } + + return true; +} + +// Write a vector as the byte representation of the contents. +// +// (This only really makes sense for a type T that has sizeof(T)==1, otherwise +// serilized representation is not endian-agnositic. But it is useful to keep +// the possibility of a greater size for experiments comparing Varint32 encoding +// of a vector of larger integrals vs a plain form.) +// +template<typename T> +void WriteVectorU8(const std::vector<T>& items, SinkStream* buffer) { + uint32 count = items.size(); + buffer->WriteVarint32(count); + if (count != 0) { + size_t byte_count = count * sizeof(T); + buffer->Write(static_cast<const void*>(&items[0]), byte_count); + } +} + +template<typename T> +bool ReadVectorU8(std::vector<T>* items, SourceStream* buffer) { + uint32 count; + if (!buffer->ReadVarint32(&count)) + return false; + + items->clear(); + items->resize(count); + if (count != 0) { + size_t byte_count = count * sizeof(T); + return buffer->Read(static_cast<void*>(&((*items)[0])), byte_count); + } + return true; +} + +//////////////////////////////////////////////////////////////////////////////// + +void EncodedProgram::DefineRel32Label(int index, RVA value) { + DefineLabelCommon(&rel32_rva_, index, value); +} + +void EncodedProgram::DefineAbs32Label(int index, RVA value) { + DefineLabelCommon(&abs32_rva_, index, value); +} + +static const RVA kUnassignedRVA = static_cast<RVA>(-1); + +void EncodedProgram::DefineLabelCommon(std::vector<RVA>* rvas, + int index, + RVA rva) { + if (static_cast<int>(rvas->size()) <= index) { + rvas->resize(index + 1, kUnassignedRVA); + } + if ((*rvas)[index] != kUnassignedRVA) { + NOTREACHED() << "DefineLabel double assigned " << index; + } + (*rvas)[index] = rva; +} + +void EncodedProgram::EndLabels() { + FinishLabelsCommon(&abs32_rva_); + FinishLabelsCommon(&rel32_rva_); +} + +void EncodedProgram::FinishLabelsCommon(std::vector<RVA>* rvas) { + // Replace all unassigned slots with the value at the previous index so they + // delta-encode to zero. (There might be better values than zero. The way to + // get that is have the higher level assembly program assign the unassigned + // slots.) + RVA previous = 0; + size_t size = rvas->size(); + for (size_t i = 0; i < size; ++i) { + if ((*rvas)[i] == kUnassignedRVA) + (*rvas)[i] = previous; + else + previous = (*rvas)[i]; + } +} + +void EncodedProgram::AddOrigin(RVA origin) { + ops_.push_back(ORIGIN); + origins_.push_back(origin); +} + +void EncodedProgram::AddCopy(int count, const void* bytes) { + const uint8* source = static_cast<const uint8*>(bytes); + + // Fold adjacent COPY instructions into one. This nearly halves the size of + // an EncodedProgram with only COPY1 instructions since there are approx plain + // 16 bytes per reloc. This has a working-set benefit during decompression. + // For compression of files with large differences this makes a small (4%) + // improvement in size. For files with small differences this degrades the + // compressed size by 1.3% + if (ops_.size() > 0) { + if (ops_.back() == COPY1) { + ops_.back() = COPY; + copy_counts_.push_back(1); + } + if (ops_.back() == COPY) { + copy_counts_.back() += count; + for (int i = 0; i < count; ++i) { + copy_bytes_.push_back(source[i]); + } + return; + } + } + + if (count == 1) { + ops_.push_back(COPY1); + copy_bytes_.push_back(source[0]); + } else { + ops_.push_back(COPY); + copy_counts_.push_back(count); + for (int i = 0; i < count; ++i) { + copy_bytes_.push_back(source[i]); + } + } +} + +void EncodedProgram::AddAbs32(int label_index) { + ops_.push_back(ABS32); + abs32_ix_.push_back(label_index); +} + +void EncodedProgram::AddRel32(int label_index) { + ops_.push_back(REL32); + rel32_ix_.push_back(label_index); +} + +void EncodedProgram::AddMakeRelocs() { + ops_.push_back(MAKE_BASE_RELOCATION_TABLE); +} + +void EncodedProgram::DebuggingSummary() { + LOG(INFO) << "EncodedProgram Summary"; + LOG(INFO) << " image base " << image_base_; + LOG(INFO) << " abs32 rvas " << abs32_rva_.size(); + LOG(INFO) << " rel32 rvas " << rel32_rva_.size(); + LOG(INFO) << " ops " << ops_.size(); + LOG(INFO) << " origins " << origins_.size(); + LOG(INFO) << " copy_counts " << copy_counts_.size(); + LOG(INFO) << " copy_bytes " << copy_bytes_.size(); + LOG(INFO) << " abs32_ix " << abs32_ix_.size(); + LOG(INFO) << " rel32_ix " << rel32_ix_.size(); +} + +//////////////////////////////////////////////////////////////////////////////// + +// For algorithm refinement purposes it is useful to write subsets of the file +// format. This gives us the ability to estimate the entropy of the +// differential compression of the individual streams, which can provide +// invaluable insights. The default, of course, is to include all the streams. +// +enum FieldSelect { + INCLUDE_ABS32_ADDRESSES = 0x0001, + INCLUDE_REL32_ADDRESSES = 0x0002, + INCLUDE_ABS32_INDEXES = 0x0010, + INCLUDE_REL32_INDEXES = 0x0020, + INCLUDE_OPS = 0x0100, + INCLUDE_BYTES = 0x0200, + INCLUDE_COPY_COUNTS = 0x0400, + INCLUDE_MISC = 0x1000 +}; + +static FieldSelect GetFieldSelect() { +#if 1 + // TODO(sra): Use better configuration. + std::wstring s = base::SysInfo::GetEnvVar(L"A_FIELDS"); + if (!s.empty()) { + return static_cast<FieldSelect>(wcstoul(s.c_str(), 0, 0)); + } +#endif + return static_cast<FieldSelect>(~0); +} + +void EncodedProgram::WriteTo(SinkStreamSet* streams) { + FieldSelect select = GetFieldSelect(); + + // The order of fields must be consistent in WriteTo and ReadFrom, regardless + // of the streams used. The code can be configured with all kStreamXXX + // constants the same. + // + // If we change the code to pipeline reading with assembly (to avoid temporary + // storage vectors by consuming operands directly from the stream) then we + // need to read the base address and the random access address tables first, + // the rest can be interleaved. + + if (select & INCLUDE_MISC) { + // TODO(sra): write 64 bits. + streams->stream(kStreamMisc)->WriteVarint32( + static_cast<uint32>(image_base_)); + } + + if (select & INCLUDE_ABS32_ADDRESSES) + WriteU32Delta(abs32_rva_, streams->stream(kStreamAbs32Addresses)); + if (select & INCLUDE_REL32_ADDRESSES) + WriteU32Delta(rel32_rva_, streams->stream(kStreamRel32Addresses)); + if (select & INCLUDE_MISC) + WriteVector(origins_, streams->stream(kStreamOriginAddresses)); + if (select & INCLUDE_OPS) { + streams->stream(kStreamOps)->Reserve(ops_.size() + 5); // 5 for length. + WriteVector(ops_, streams->stream(kStreamOps)); + } + if (select & INCLUDE_COPY_COUNTS) + WriteVector(copy_counts_, streams->stream(kStreamCopyCounts)); + if (select & INCLUDE_BYTES) + WriteVectorU8(copy_bytes_, streams->stream(kStreamBytes)); + if (select & INCLUDE_ABS32_INDEXES) + WriteVector(abs32_ix_, streams->stream(kStreamAbs32Indexes)); + if (select & INCLUDE_REL32_INDEXES) + WriteVector(rel32_ix_, streams->stream(kStreamRel32Indexes)); +} + +bool EncodedProgram::ReadFrom(SourceStreamSet* streams) { + // TODO(sra): read 64 bits. + uint32 temp; + if (!streams->stream(kStreamMisc)->ReadVarint32(&temp)) + return false; + image_base_ = temp; + + if (!ReadU32Delta(&abs32_rva_, streams->stream(kStreamAbs32Addresses))) + return false; + if (!ReadU32Delta(&rel32_rva_, streams->stream(kStreamRel32Addresses))) + return false; + if (!ReadVector(&origins_, streams->stream(kStreamOriginAddresses))) + return false; + if (!ReadVector(&ops_, streams->stream(kStreamOps))) + return false; + if (!ReadVector(©_counts_, streams->stream(kStreamCopyCounts))) + return false; + if (!ReadVectorU8(©_bytes_, streams->stream(kStreamBytes))) + return false; + if (!ReadVector(&abs32_ix_, streams->stream(kStreamAbs32Indexes))) + return false; + if (!ReadVector(&rel32_ix_, streams->stream(kStreamRel32Indexes))) + return false; + + // Check that streams have been completely consumed. + for (int i = 0; i < kStreamLimit; ++i) { + if (streams->stream(i)->Remaining() > 0) + return false; + } + + return true; +} + +// Safe, non-throwing version of std::vector::at(). Returns 'true' for success, +// 'false' for out-of-bounds index error. +template<typename T> +bool VectorAt(const std::vector<T>& v, size_t index, T* output) { + if (index >= v.size()) + return false; + *output = v[index]; + return true; +} + +bool EncodedProgram::AssembleTo(SinkStream* final_buffer) { + // For the most part, the assembly process walks the various tables. + // ix_mumble is the index into the mumble table. + size_t ix_origins = 0; + size_t ix_copy_counts = 0; + size_t ix_copy_bytes = 0; + size_t ix_abs32_ix = 0; + size_t ix_rel32_ix = 0; + + RVA current_rva = 0; + + bool pending_base_relocation_table = false; + SinkStream bytes_following_base_relocation_table; + + SinkStream* output = final_buffer; + + for (size_t ix_ops = 0; ix_ops < ops_.size(); ++ix_ops) { + OP op = ops_[ix_ops]; + + switch (op) { + default: + return false; + + case ORIGIN: { + RVA section_rva; + if (!VectorAt(origins_, ix_origins, §ion_rva)) + return false; + ++ix_origins; + current_rva = section_rva; + break; + } + + case COPY: { + int count; + if (!VectorAt(copy_counts_, ix_copy_counts, &count)) + return false; + ++ix_copy_counts; + for (int i = 0; i < count; ++i) { + uint8 b; + if (!VectorAt(copy_bytes_, ix_copy_bytes, &b)) + return false; + ++ix_copy_bytes; + output->Write(&b, 1); + } + current_rva += count; + break; + } + + case COPY1: { + uint8 b; + if (!VectorAt(copy_bytes_, ix_copy_bytes, &b)) + return false; + ++ix_copy_bytes; + output->Write(&b, 1); + current_rva += 1; + break; + } + + case REL32: { + uint32 index; + if (!VectorAt(rel32_ix_, ix_rel32_ix, &index)) + return false; + ++ix_rel32_ix; + RVA rva; + if (!VectorAt(rel32_rva_, index, &rva)) + return false; + uint32 offset = (rva - (current_rva + 4)); + output->Write(&offset, 4); + current_rva += 4; + break; + } + + case ABS32: { + uint32 index; + if (!VectorAt(abs32_ix_, ix_abs32_ix, &index)) + return false; + ++ix_abs32_ix; + RVA rva; + if (!VectorAt(abs32_rva_, index, &rva)) + return false; + uint32 abs32 = static_cast<uint32>(rva + image_base_); + abs32_relocs_.push_back(current_rva); + output->Write(&abs32, 4); + current_rva += 4; + break; + } + + case MAKE_BASE_RELOCATION_TABLE: { + // We can see the base relocation anywhere, but we only have the + // information to generate it at the very end. So we divert the bytes + // we are generating to a temporary stream. + if (pending_base_relocation_table) // Can't have two base relocation + // tables. + return false; + + pending_base_relocation_table = true; + output = &bytes_following_base_relocation_table; + break; + // There is a potential problem *if* the instruction stream contains + // some REL32 relocations following the base relocation and in the same + // section. We don't know the size of the table, so 'current_rva' will + // be wrong, causing REL32 offsets to be miscalculated. This never + // happens; the base relocation table is usually in a section of its + // own, a data-only section, and following everything else in the + // executable except some padding zero bytes. We could fix this by + // emitting an ORIGIN after the MAKE_BASE_RELOCATION_TABLE. + } + } + } + + if (pending_base_relocation_table) { + GenerateBaseRelocations(final_buffer); + final_buffer->Append(&bytes_following_base_relocation_table); + } + + // Final verification check: did we consume all lists? + if (ix_copy_counts != copy_counts_.size()) + return false; + if (ix_copy_bytes != copy_bytes_.size()) + return false; + if (ix_abs32_ix != abs32_ix_.size()) + return false; + if (ix_rel32_ix != rel32_ix_.size()) + return false; + + return true; +} + + +// RelocBlock has the layout of a block of relocations in the base relocation +// table file format. +// +class RelocBlock { + public: + uint32 page_rva; + uint32 block_size; + uint16 relocs[4096]; // Allow up to one relocation per byte of a 4k page. + + RelocBlock() : page_rva(~0), block_size(8) {} + + void Add(uint16 item) { + relocs[(block_size-8)/2] = item; + block_size += 2; + } + + void Flush(SinkStream* buffer) { + if (block_size != 8) { + if (block_size % 4 != 0) { // Pad to make size multiple of 4 bytes. + Add(0); + } + buffer->Write(this, block_size); + block_size = 8; + } + } +}; + +COMPILE_ASSERT(offsetof(RelocBlock, relocs) == 8, reloc_block_header_size); + +void EncodedProgram::GenerateBaseRelocations(SinkStream* buffer) { + std::sort(abs32_relocs_.begin(), abs32_relocs_.end()); + + RelocBlock block; + + for (size_t i = 0; i < abs32_relocs_.size(); ++i) { + uint32 rva = abs32_relocs_[i]; + uint32 page_rva = rva & ~0xFFF; + if (page_rva != block.page_rva) { + block.Flush(buffer); + block.page_rva = page_rva; + } + block.Add(0x3000 | (rva & 0xFFF)); + } + block.Flush(buffer); +} + +//////////////////////////////////////////////////////////////////////////////// + +Status WriteEncodedProgram(EncodedProgram* encoded, SinkStreamSet* sink) { + encoded->WriteTo(sink); + return C_OK; +} + +Status ReadEncodedProgram(SourceStreamSet* streams, EncodedProgram** output) { + EncodedProgram* encoded = new EncodedProgram(); + if (encoded->ReadFrom(streams)) { + *output = encoded; + return C_OK; + } + delete encoded; + return C_DESERIALIZATION_FAILED; +} + +Status Assemble(EncodedProgram* encoded, SinkStream* buffer) { + bool assembled = encoded->AssembleTo(buffer); + if (assembled) + return C_OK; + return C_ASSEMBLY_FAILED; +} + +void DeleteEncodedProgram(EncodedProgram* encoded) { + delete encoded; +} + +} // end namespace diff --git a/third_party/courgette/encoded_program.h b/third_party/courgette/encoded_program.h new file mode 100644 index 0000000..7331042 --- /dev/null +++ b/third_party/courgette/encoded_program.h @@ -0,0 +1,84 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef COURGETTE_ENCODED_PROGRAM_H_ +#define COURGETTE_ENCODED_PROGRAM_H_ + +#include <vector> + +#include "base/basictypes.h" +#include "third_party/courgette/image_info.h" + +namespace courgette { + +class SinkStream; +class SinkStreamSet; +class SourceStreamSet; + +// An EncodedProgram is a set of tables that contain a simple 'binary assembly +// language' that can be assembled to produce a sequence of bytes, for example, +// a Windows 32-bit executable. +// +class EncodedProgram { + public: + EncodedProgram(); + ~EncodedProgram(); + + // Generating an EncodedProgram: + // + // (1) The image base can be specified at any time. + void set_image_base(uint64 base) { image_base_ = base; } + + // (2) Address tables and indexes defined first. + void DefineRel32Label(int index, RVA address); + void DefineAbs32Label(int index, RVA address); + void EndLabels(); + + // (3) Add instructions in the order needed to generate bytes of file. + void AddOrigin(RVA rva); + void AddCopy(int count, const void* bytes); + void AddRel32(int label_index); + void AddAbs32(int label_index); + void AddMakeRelocs(); + + // (3) Serialize binary assembly language tables to a set of streams. + void WriteTo(SinkStreamSet *streams); + + // Using an EncodedProgram to generate a byte stream: + // + // (4) Deserializes a fresh EncodedProgram from a set of streams. + bool ReadFrom(SourceStreamSet *streams); + + // (5) Assembles the 'binary assembly language' into final file. + bool AssembleTo(SinkStream *buffer); + + private: + enum OP; // Binary assembly language operations. + + void DebuggingSummary(); + void GenerateBaseRelocations(SinkStream *buffer); + void DefineLabelCommon(std::vector<RVA>*, int, RVA); + void FinishLabelsCommon(std::vector<RVA>* addresses); + + // Binary assembly language tables. + uint64 image_base_; + std::vector<RVA> rel32_rva_; + std::vector<RVA> abs32_rva_; + std::vector<OP> ops_; + std::vector<RVA> origins_; + std::vector<int> copy_counts_; + std::vector<uint8> copy_bytes_; + std::vector<uint32> rel32_ix_; + std::vector<uint32> abs32_ix_; + + // Table of the addresses containing abs32 relocations; computed during + // assembly, used to generate base relocation table. + std::vector<uint32> abs32_relocs_; + + DISALLOW_COPY_AND_ASSIGN(EncodedProgram); +}; + +} // namespace courgette +#endif // COURGETTE_ENCODED_FORMAT_H_ + diff --git a/third_party/courgette/encoded_program_fuzz_unittest.cc b/third_party/courgette/encoded_program_fuzz_unittest.cc new file mode 100644 index 0000000..9cd5020 --- /dev/null +++ b/third_party/courgette/encoded_program_fuzz_unittest.cc @@ -0,0 +1,236 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Fuzz testing for EncodedProgram serialized format and assembly.
+//
+// We would like some assurance that if an EncodedProgram is malformed we will
+// not crash. The EncodedProgram could be malformed either due to malicious
+// attack to due to an error in patch generation.
+//
+// We try a lot of arbitrary modifications to the serialized form and make sure
+// that the outcome is not a crash.
+
+#include <string>
+
+#include "base/path_service.h"
+#include "base/file_util.h"
+#include "base/string_util.h"
+#include "base/test_suite.h"
+
+#include "third_party/courgette/courgette.h"
+#include "third_party/courgette/streams.h"
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+class DecodeFuzzTest : public testing::Test {
+ public:
+ void FuzzExe(const char *) const;
+
+ private:
+ virtual void SetUp() {
+ PathService::Get(base::DIR_SOURCE_ROOT, &testdata_dir_);
+ // testdata_dir_ = testdata_dir_.Append(L"third_party");
+ testdata_dir_ = testdata_dir_.Append(L"courgette");
+ testdata_dir_ = testdata_dir_.Append(L"testdata");
+ }
+
+ virtual void TearDown() { }
+
+ void FuzzByte(const std::string& buffer, const std::string& output,
+ size_t index) const;
+ void FuzzBits(const std::string& buffer, const std::string& output,
+ size_t index, int bits_to_flip) const;
+
+ // Returns true if could assemble, false if rejected.
+ bool TryAssemble(const std::string& buffer, std::string* output) const;
+
+ // Returns contents of |file_name| as uninterprested bytes stored in a string.
+ std::string FileContents(const char* file_name) const;
+
+ // Full path name of testdata directory
+ FilePath testdata_dir_;
+};
+
+// Reads a test file into a string.
+std::string DecodeFuzzTest::FileContents(const char* file_name) const {
+ FilePath file_path = testdata_dir_.AppendASCII(file_name);
+ std::string file_contents;
+ if (!file_util::ReadFileToString(file_path, &file_contents)) {
+ EXPECT_TRUE(!"Could not read test data");
+ }
+ return file_contents;
+}
+
+// Loads an executable and does fuzz testing in the serialized format.
+void DecodeFuzzTest::FuzzExe(const char* file_name) const {
+ std::string file1 = FileContents(file_name);
+
+ const void* original_buffer = file1.c_str();
+ size_t original_length = file1.size();
+
+ courgette::AssemblyProgram* program = NULL;
+ const courgette::Status parse_status =
+ courgette::ParseWin32X86PE(original_buffer, original_length, &program);
+ EXPECT_EQ(courgette::C_OK, parse_status);
+
+ courgette::EncodedProgram* encoded = NULL;
+
+ const courgette::Status encode_status = Encode(program, &encoded);
+ EXPECT_EQ(courgette::C_OK, encode_status);
+
+ DeleteAssemblyProgram(program);
+
+ courgette::SinkStreamSet sinks;
+ const courgette::Status write_status = WriteEncodedProgram(encoded, &sinks);
+ EXPECT_EQ(courgette::C_OK, write_status);
+
+ DeleteEncodedProgram(encoded);
+
+ courgette::SinkStream sink;
+ bool can_collect = sinks.CopyTo(&sink);
+ EXPECT_TRUE(can_collect);
+
+ size_t length = sink.Length();
+
+ std::string base_buffer(reinterpret_cast<const char*>(sink.Buffer()), length);
+ std::string base_output;
+ bool ok = TryAssemble(base_buffer, &base_output);
+ EXPECT_EQ(true, ok);
+
+ // Now we have a good serialized EncodedProgram in |base_buffer|. Time to
+ // fuzz.
+
+ // More intense fuzzing on the first part because it contains more control
+ // information like substeam lengths.
+ size_t position = 0;
+ for ( ; position < 100 && position < length; position += 1) {
+ FuzzByte(base_buffer, base_output, position);
+ }
+ // We would love to fuzz every position, but it takes too long.
+ for ( ; position < length; position += 900) {
+ FuzzByte(base_buffer, base_output, position);
+ }
+}
+
+// FuzzByte tries to break the EncodedProgram deserializer and assembler. It
+// takes a good serialization of and EncodedProgram, flips some bits, and checks
+// that the behaviour is reasonable. It has testing checks for unreasonable
+// behaviours.
+void DecodeFuzzTest::FuzzByte(const std::string& base_buffer,
+ const std::string& base_output,
+ size_t index) const {
+ printf("Fuzzing position %d\n", static_cast<int>(index));
+
+ // The following 10 values are a compromize between run time and coverage of
+ // the 255 'wrong' values at this byte position.
+
+ // 0xFF flips all the bits.
+ FuzzBits(base_buffer, base_output, index, 0xFF);
+ // 0x7F flips the most bits without changing Varint32 framing.
+ FuzzBits(base_buffer, base_output, index, 0x7F);
+ // These all flip one bit.
+ FuzzBits(base_buffer, base_output, index, 0x80);
+ FuzzBits(base_buffer, base_output, index, 0x40);
+ FuzzBits(base_buffer, base_output, index, 0x20);
+ FuzzBits(base_buffer, base_output, index, 0x10);
+ FuzzBits(base_buffer, base_output, index, 0x08);
+ FuzzBits(base_buffer, base_output, index, 0x04);
+ FuzzBits(base_buffer, base_output, index, 0x02);
+ FuzzBits(base_buffer, base_output, index, 0x01);
+}
+
+// FuzzBits tries to break the EncodedProgram deserializer and assembler. It
+// takes a good serialization of and EncodedProgram, flips some bits, and checks
+// that the behaviour is reasonable.
+//
+// There are EXPECT calls to check for unreasonable behaviour. These are
+// somewhat arbitrary in that the parameters cannot easily be derived from first
+// principles. They may need updating as the serialized format evolves.
+void DecodeFuzzTest::FuzzBits(const std::string& base_buffer,
+ const std::string& base_output,
+ size_t index, int bits_to_flip) const {
+ std::string modified_buffer = base_buffer;
+ std::string modified_output;
+ modified_buffer[index] ^= bits_to_flip;
+
+ bool ok = TryAssemble(modified_buffer, &modified_output);
+
+ if (ok) {
+ // We normally expect TryAssemble to fail. But sometimes it succeeds.
+ // What could have happened? We changed one byte in the serialized form:
+ //
+ // * If we changed one of the copied bytes, we would see a single byte
+ // change in the output.
+ // * If we changed an address table element, all the references to that
+ // address would be different.
+ // * If we changed a copy count, we would run out of data in some stream,
+ // or leave data remaining, so should not be here.
+ // * If we changed an origin address, it could affect all relocations based
+ // off that address. If no relocations were based off the address then
+ // there will be no changes.
+ // * If we changed an origin address, it could cause some abs32 relocs to
+ // shift from one page to the next, changing the number and layout of
+ // blocks in the base relocation table.
+
+ // Generated length could vary slightly due to base relocation table layout.
+ // In the worst case the number of base relocation blocks doubles, approx
+ // 12/4096 or 0.3% size of file.
+ size_t base_length = base_output.length();
+ size_t modified_length = modified_output.length();
+ ptrdiff_t diff = base_length - modified_length;
+ if (diff < -200 || diff > 200) {
+ EXPECT_EQ(base_length, modified_length);
+ }
+
+ size_t changed_byte_count = 0;
+ for (size_t i = 0; i < base_length && i < modified_length; ++i) {
+ changed_byte_count += (base_output[i] != modified_output[i]);
+ }
+
+ if (index > 60) { // Beyond the origin addresses ...
+ EXPECT_NE(0, changed_byte_count); // ... we expect some difference.
+ }
+ // Currently all changes are smaller than this number:
+ EXPECT_GE(45000u, changed_byte_count);
+ }
+}
+
+bool DecodeFuzzTest::TryAssemble(const std::string& buffer,
+ std::string* output) const {
+ courgette::EncodedProgram *encoded = NULL;
+ bool result = false;
+
+ courgette::SourceStreamSet sources;
+ bool can_get_source_streams = sources.Init(buffer.c_str(), buffer.length());
+ if (can_get_source_streams) {
+ const courgette::Status read_status =
+ ReadEncodedProgram(&sources, &encoded);
+ if (read_status == courgette::C_OK) {
+ courgette::SinkStream assembled;
+ const courgette::Status assemble_status = Assemble(encoded, &assembled);
+
+ if (assemble_status == courgette::C_OK) {
+ const void* assembled_buffer = assembled.Buffer();
+ size_t assembled_length = assembled.Length();
+
+ output->clear();
+ output->assign(reinterpret_cast<const char*>(assembled_buffer),
+ assembled_length);
+ result = true;
+ }
+ }
+ }
+
+ DeleteEncodedProgram(encoded);
+
+ return result;
+}
+
+TEST_F(DecodeFuzzTest, All) {
+ FuzzExe("setup1.exe");
+}
+
+int main(int argc, char** argv) {
+ return TestSuite(argc, argv).Run();
+}
diff --git a/third_party/courgette/encoded_program_unittest.cc b/third_party/courgette/encoded_program_unittest.cc new file mode 100644 index 0000000..9b0025e --- /dev/null +++ b/third_party/courgette/encoded_program_unittest.cc @@ -0,0 +1,65 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "third_party/courgette/encoded_program.h" + +#include "third_party/courgette/streams.h" +#include "testing/gtest/include/gtest/gtest.h" + +TEST(EncodedProgramTest, Test) { + // + // Create a simple program with a few addresses and references and + // check that the bits produced are as expected. + // + courgette::EncodedProgram* program = new courgette::EncodedProgram(); + + uint32 base = 0x00900000; + program->set_image_base(base); + + program->DefineRel32Label(5, 0); // REL32 index 5 == base + 0 + program->DefineAbs32Label(7, 4); // ABS32 index 7 == base + 4 + program->EndLabels(); + + program->AddOrigin(0); // Start at base. + program->AddAbs32(7); + program->AddRel32(5); + + // Serialize and deserialize. + + courgette::SinkStreamSet sinks; + program->WriteTo(&sinks); + + courgette::SinkStream sink; + bool can_collect = sinks.CopyTo(&sink); + EXPECT_TRUE(can_collect); + + const void* buffer = sink.Buffer(); + size_t length = sink.Length(); + + courgette::SourceStreamSet sources; + bool can_get_source_streams = sources.Init(buffer, length); + EXPECT_TRUE(can_get_source_streams); + + courgette::EncodedProgram *encoded2 = new courgette::EncodedProgram(); + bool can_read = encoded2->ReadFrom(&sources); + EXPECT_TRUE(can_read); + + // Finally, try to assemble. + courgette::SinkStream assembled; + bool can_assemble = encoded2->AssembleTo(&assembled); + EXPECT_TRUE(can_assemble); + + const void* assembled_buffer = assembled.Buffer(); + size_t assembled_length = assembled.Length(); + + EXPECT_EQ(8, assembled_length); + + static const uint8 golden[] = { + 0x04, 0x00, 0x90, 0x00, // ABS32 to base + 4 + 0xF8, 0xFF, 0xFF, 0xFF // REL32 from next line to base + 2 + }; + + EXPECT_EQ(0, memcmp(assembled_buffer, golden, 8)); +} + diff --git a/third_party/courgette/ensemble.cc b/third_party/courgette/ensemble.cc new file mode 100644 index 0000000..4c8f013 --- /dev/null +++ b/third_party/courgette/ensemble.cc @@ -0,0 +1,102 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// *** File comments
+
+#include "third_party/courgette/ensemble.h"
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+#include "base/string_util.h"
+
+#include "third_party/courgette/image_info.h"
+#include "third_party/courgette/region.h"
+#include "third_party/courgette/streams.h"
+#include "third_party/courgette/simple_delta.h"
+
+namespace courgette {
+
+Element::Element(Kind kind, Ensemble* ensemble, const Region& region)
+ : kind_(kind), ensemble_(ensemble), region_(region) {
+}
+
+std::string Element::Name() const {
+ return ensemble_->name() + "("
+ + IntToString(kind()) + ","
+ + Uint64ToString(offset_in_ensemble()) + ","
+ + Uint64ToString(region().length()) + ")";
+}
+
+// A subclass of Element that has a PEInfo.
+class ElementWinPE : public Element {
+ public:
+ ElementWinPE(Kind kind, Ensemble* ensemble, const Region& region,
+ PEInfo* info)
+ : Element(kind, ensemble, region),
+ pe_info_(info) {
+ }
+
+ virtual PEInfo* GetPEInfo() const { return pe_info_; }
+
+ protected:
+ ~ElementWinPE() { delete pe_info_; }
+
+ private:
+ PEInfo* pe_info_; // Owned by |this|.
+};
+
+// Scans the Ensemble's region, sniffing out Elements. We assume that the
+// elements do not overlap.
+Status Ensemble::FindEmbeddedElements() {
+ size_t length = region_.length();
+ const uint8* start = region_.start();
+
+ size_t position = 0;
+ while (position < length) {
+ // Quick test; Windows executables begin with 'MZ'.
+ if (start[position] == 'M' &&
+ position + 1 < length && start[position + 1] == 'Z') {
+ courgette::PEInfo *info = new courgette::PEInfo();
+ info->Init(start + position, length - position);
+ if (info->ParseHeader()) {
+ Region region(start + position, info->length());
+
+ if (info->has_text_section()) {
+ Element* element = new ElementWinPE(Element::WIN32_X86_WITH_CODE,
+ this, region, info);
+ owned_elements_.push_back(element);
+ elements_.push_back(element);
+ position += region.length();
+ continue;
+ }
+
+ // If we had a clever transformation for resource-only executables we
+ // should identify the suitable elements here:
+ if (!info->has_text_section() && false) {
+ Element* element = new ElementWinPE(Element::WIN32_NOCODE,
+ this, region, info);
+ owned_elements_.push_back(element);
+ elements_.push_back(element);
+ position += region.length();
+ continue;
+ }
+ }
+ delete info;
+ }
+
+ // This is where to add new formats, e.g. Linux executables, Dalvik
+ // executables etc.
+
+ // No Element found at current position.
+ ++position;
+ }
+ return C_OK;
+}
+
+Ensemble::~Ensemble() {
+ for (size_t i = 0; i < owned_elements_.size(); ++i)
+ delete owned_elements_[i];
+}
+
+} // namespace
diff --git a/third_party/courgette/ensemble.h b/third_party/courgette/ensemble.h new file mode 100644 index 0000000..7602c3f --- /dev/null +++ b/third_party/courgette/ensemble.h @@ -0,0 +1,257 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// The main idea in Courgette is to do patching *under a tranformation*. The
+// input is transformed into a new representation, patching occurs in the new
+// repesentation, and then the tranform is reversed to get the patched data.
+//
+// The idea is applied to pieces (or 'Elements') of the whole (or 'Ensemble').
+// Each of the elements has to go through the same set of steps in lock-step,
+// but there may be many different kinds of elements, which have different
+// transformation.
+//
+// This file declares all the main types involved in creating and applying a
+// patch with this structure.
+
+#ifndef COURGETTE_ENSEMBLE_H_
+#define COURGETTE_ENSEMBLE_H_
+
+#include <vector>
+#include <string>
+
+#include "base/basictypes.h"
+
+#include "third_party/courgette/courgette.h"
+#include "third_party/courgette/region.h"
+#include "third_party/courgette/streams.h"
+
+namespace courgette {
+
+// Forward declarations:
+class Ensemble;
+class PEInfo;
+
+// An Element is a region of an Ensemble with an identifyable kind.
+//
+class Element {
+ public:
+ enum Kind { WIN32_X86_WITH_CODE, WIN32_NOCODE };
+
+ virtual ~Element() {}
+
+ Kind kind() const { return kind_; }
+ const Region& region() const { return region_; }
+
+ // The name is used only for debugging and logging.
+ virtual std::string Name() const;
+
+ // Returns the byte position of this Element relative to the start of
+ // containing Ensemble.
+ size_t offset_in_ensemble() const;
+
+ // Some subclasses of Element might have a PEInfo.
+ virtual PEInfo* GetPEInfo() const { return NULL; }
+
+ protected:
+ Element(Kind kind, Ensemble* ensemble, const Region& region);
+
+ private:
+ Kind kind_;
+ Ensemble* ensemble_;
+ Region region_;
+
+ DISALLOW_COPY_AND_ASSIGN(Element);
+};
+
+
+class Ensemble {
+ public:
+ Ensemble(const Region& region, const char* name)
+ : region_(region), name_(name) {}
+ ~Ensemble();
+
+ const Region& region() const { return region_; }
+ const std::string& name() const { return name_; }
+
+ // Scans the region to find Elements within the region().
+ Status FindEmbeddedElements();
+
+ // Returns the elements found by 'FindEmbeddedElements'.
+ const std::vector<Element*>& elements() const { return elements_; }
+
+
+ private:
+ Region region_; // The memory, owned by caller, containing the
+ // Ensemble's data.
+ std::string name_; // A debugging/logging name for the Ensemble.
+
+ std::vector<Element*> elements_; // Embedded elements discovered.
+ std::vector<Element*> owned_elements_; // For deallocation.
+
+ DISALLOW_COPY_AND_ASSIGN(Ensemble);
+};
+
+inline size_t Element::offset_in_ensemble() const {
+ return region().start() - ensemble_->region().start();
+}
+
+// The 'CourgettePatchFile' is class is a 'namespace' for the constants that
+// appear in a Courgette patch file.
+struct CourgettePatchFile {
+ //
+ // The Courgette patch format interleaves the data for N embedded Elements.
+ //
+ // Format of a patch file:
+ // header:
+ // magic
+ // version
+ // source-checksum
+ // target-checksum
+ // multiple-streams:
+ // stream 0:
+ // number-of-transformed-elements (N) - varint32
+ // transformation-1-method-id
+ // transformation-2-method-id
+ // ...
+ // transformation-1-initial-parameters
+ // transformation-2-initial-parameters
+ // ...
+ // stream 1:
+ // correction:
+ // transformation-1-parameters
+ // transformation-2-parameters
+ // ...
+ // stream 2:
+ // correction:
+ // transformed-element-1
+ // transformed-element-2
+ // ...
+ // stream 3:
+ // correction:
+ // base-file
+ // element-1
+ // element-2
+ // ...
+
+ static const uint32 kMagic = 'C' | ('o' << 8) | ('u' << 16);
+
+ static const uint32 kVersion = 20090320;
+
+ // Transformation method IDs.
+ enum TransformationMethodId {
+ T_COURGETTE_WIN32_X86 = 1, // Windows 32 bit 'Portable Executable' x86.
+ };
+};
+
+// For any transform you would implement both a TransformationPatcher and a
+// TransformationPatchGenerator.
+//
+// TransformationPatcher is the interface which abstracts out the actual
+// transformation used on an Element. The patching itself happens outside the
+// actions of a TransformationPatcher. There are four steps.
+//
+// The first step is an Init step. The parameters to the Init step identify the
+// element, for example, range of locations within the original ensemble that
+// correspond to the element.
+//
+// PredictTransformParameters, explained below.
+//
+// The two final steps are 'Transform' - to transform the element into a new
+// representation, and to 'Reform' - to transform from the new representation
+// back to the original form.
+//
+// The Transform step takes some parameters. This allows the transform to be
+// customized to the particular element, or to receive some assistance in the
+// analysis required to perform the transform. The transform parameters might
+// be extensive but mostly predicable, so preceeding Transform is a
+// PredictTransformParameters step.
+//
+class TransformationPatcher {
+ public:
+ virtual ~TransformationPatcher() {}
+
+ // First step: provides parameters for the patching. This would at a minimum
+ // identify the element within the ensemble being patched.
+ virtual Status Init(SourceStream* parameter_stream) = 0;
+
+ // Second step: predicts transform parameters.
+ virtual Status PredictTransformParameters(
+ SinkStreamSet* predicted_parameters) = 0;
+
+ // Third step: transforms element from original representation into alternate
+ // representation.
+ virtual Status Transform(SourceStreamSet* corrected_parameters,
+ SinkStreamSet* transformed_element) = 0;
+
+ // Final step: transforms element back from alternate representation into
+ // original representation.
+ virtual Status Reform(SourceStreamSet* transformed_element,
+ SinkStream* reformed_element) = 0;
+};
+
+// TransformationPatchGenerator is the interface which abstracts out the actual
+// transformation used (and adjustment used) when differentially compressing one
+// Element from the |new_ensemble| against a corresponding element in the
+// |old_ensemble|.
+//
+// This is not a pure interface. There is a small amount of inheritance
+// implementation for the fields and actions common to all
+// TransformationPatchGenerators.
+//
+// When TransformationPatchGenerator is subclassed, there will be a
+// corresponding subclass of TransformationPatcher.
+//
+class TransformationPatchGenerator {
+ public:
+ TransformationPatchGenerator(Element* old_element,
+ Element* new_element,
+ TransformationPatcher* patcher);
+
+ virtual ~TransformationPatchGenerator();
+
+ // Returns the TransformationMethodId that identies this transformation.
+ virtual CourgettePatchFile::TransformationMethodId Kind() = 0;
+
+ // Writes the parameters that will be passed to TransformationPatcher::Init.
+ virtual Status WriteInitialParameters(SinkStream* parameter_stream) = 0;
+
+ // Predicts the transform parameters for the |old_element|. This must match
+ // exactly the output that will be produced by the PredictTransformParameters
+ // method of the corresponding subclass of TransformationPatcher. This method
+ // is not pure. The default implementation delegates to the patcher to
+ // guarantee matching output.
+ virtual Status PredictTransformParameters(SinkStreamSet* prediction);
+
+ // Writes the desired parameters for the transform of the old element from the
+ // file representation to the alternate representation.
+ virtual Status CorrectedTransformParameters(SinkStreamSet* parameters) = 0;
+
+ // Writes both |old_element| and |new_element| in the new representation.
+ // |old_corrected_parameters| will match the |corrected_parameters| passed to
+ // the Transform method of the corresponding sublcass of
+ // TransformationPatcher.
+ //
+ // The output written to |old_transformed_element| must match exactly the
+ // output written by the Transform method of the corresponding subclass of
+ // TransformationPatcher.
+ virtual Status Transform(SourceStreamSet* old_corrected_parameters,
+ SinkStreamSet* old_transformed_element,
+ SinkStreamSet* new_transformed_element) = 0;
+
+ // Transforms the new transformed_element back from the alternate
+ // representation into the original file format. This must match exactly the
+ // output that will be produced by the corresponding subclass of
+ // TransformationPatcher::Reform. This method is not pure. The default
+ // implementation delegates to the patcher.
+ virtual Status Reform(SourceStreamSet* transformed_element,
+ SinkStream* reformed_element);
+
+ protected:
+ Element* old_element_;
+ Element* new_element_;
+ TransformationPatcher* patcher_;
+};
+
+} // namespace
+#endif // COURGETTE_ENSEMBLE_H_
diff --git a/third_party/courgette/ensemble_apply.cc b/third_party/courgette/ensemble_apply.cc new file mode 100644 index 0000000..7954ca4 --- /dev/null +++ b/third_party/courgette/ensemble_apply.cc @@ -0,0 +1,412 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// This file contains the code to apply a Courgette patch.
+
+#include "third_party/courgette/ensemble.h"
+
+#include "base/basictypes.h"
+#include "base/file_util.h"
+#include "base/logging.h"
+
+#include "third_party/courgette/crc.h"
+#include "third_party/courgette/image_info.h"
+#include "third_party/courgette/region.h"
+#include "third_party/courgette/streams.h"
+#include "third_party/courgette/simple_delta.h"
+#include "third_party/courgette/win32_x86_patcher.h"
+
+namespace courgette {
+
+// EnsemblePatchApplication is all the logic and data required to apply the
+// multi-stage patch.
+class EnsemblePatchApplication {
+ public:
+ EnsemblePatchApplication();
+ ~EnsemblePatchApplication();
+
+ Status ReadHeader(SourceStream* header_stream);
+
+ Status InitBase(const Region& region);
+
+ Status ValidateBase();
+
+ Status ReadInitialParameters(SourceStream* initial_parameters);
+
+ Status PredictTransformParameters(SinkStreamSet* predicted_parameters);
+
+ Status SubpatchTransformParameters(SinkStreamSet* prediction,
+ SourceStream* correction,
+ SourceStreamSet* corrected_parameters);
+
+ Status TransformUp(SourceStreamSet* parameters,
+ SinkStreamSet* transformed_elements);
+
+ Status SubpatchTransformedElements(SinkStreamSet* elements,
+ SourceStream* correction,
+ SourceStreamSet* corrected_elements);
+
+ Status TransformDown(SourceStreamSet* transformed_elements,
+ SinkStream* basic_elements);
+
+ Status SubpatchFinalOutput(SourceStream* original,
+ SourceStream* correction,
+ SinkStream* corrected_ensemble);
+
+ private:
+ Status SubpatchStreamSets(SinkStreamSet* predicted_items,
+ SourceStream* correction,
+ SourceStreamSet* corrected_items,
+ SinkStream* corrected_items_storage);
+
+ Region base_region_; // Location of in-memory copy of 'old' version.
+
+ uint32 source_checksum_;
+ uint32 target_checksum_;
+
+ std::vector<TransformationPatcher*> patchers_;
+
+ SinkStream corrected_parameters_storage_;
+ SinkStream corrected_elements_storage_;
+
+ DISALLOW_COPY_AND_ASSIGN(EnsemblePatchApplication);
+};
+
+EnsemblePatchApplication::EnsemblePatchApplication()
+ : source_checksum_(0), target_checksum_(0) {
+}
+
+EnsemblePatchApplication::~EnsemblePatchApplication() {
+ for (size_t i = 0; i < patchers_.size(); ++i) {
+ delete patchers_[i];
+ }
+}
+
+Status EnsemblePatchApplication::ReadHeader(SourceStream* header_stream) {
+ uint32 magic;
+ if (!header_stream->ReadVarint32(&magic))
+ return C_BAD_ENSEMBLE_MAGIC;
+
+ if (magic != CourgettePatchFile::kMagic)
+ return C_BAD_ENSEMBLE_MAGIC;
+
+ uint32 version;
+ if (!header_stream->ReadVarint32(&version))
+ return C_BAD_ENSEMBLE_VERSION;
+
+ if (version != CourgettePatchFile::kVersion)
+ return C_BAD_ENSEMBLE_VERSION;
+
+ if (!header_stream->ReadVarint32(&source_checksum_))
+ return C_BAD_ENSEMBLE_HEADER;
+
+ if (!header_stream->ReadVarint32(&target_checksum_))
+ return C_BAD_ENSEMBLE_HEADER;
+
+ return C_OK;
+}
+
+Status EnsemblePatchApplication::InitBase(const Region& region) {
+ base_region_.assign(region);
+ return C_OK;
+}
+
+Status EnsemblePatchApplication::ValidateBase() {
+ uint32 checksum = CalculateCrc(base_region_.start(), base_region_.length());
+ if (source_checksum_ != checksum)
+ return C_BAD_ENSEMBLE_CRC;
+
+ return C_OK;
+}
+
+Status EnsemblePatchApplication::ReadInitialParameters(
+ SourceStream* transformation_parameters) {
+ uint32 number_of_transformations = 0;
+ if (!transformation_parameters->ReadVarint32(&number_of_transformations))
+ return C_BAD_ENSEMBLE_HEADER;
+
+ for (size_t i = 0; i < number_of_transformations; ++i) {
+ uint32 kind;
+ if (!transformation_parameters->ReadVarint32(&kind))
+ return C_BAD_ENSEMBLE_HEADER;
+
+ if (kind == CourgettePatchFile::T_COURGETTE_WIN32_X86) {
+ TransformationPatcher* patcher =
+ new CourgetteWin32X86Patcher(base_region_);
+ patchers_.push_back(patcher);
+ } else {
+ return C_BAD_ENSEMBLE_HEADER;
+ }
+ }
+
+ for (size_t i = 0; i < patchers_.size(); ++i) {
+ Status status = patchers_[i]->Init(transformation_parameters);
+ if (status != C_OK)
+ return status;
+ }
+
+ // All transformation_parameters should have been consumed by the above loop.
+ if (!transformation_parameters->Empty())
+ return C_BAD_ENSEMBLE_HEADER;
+
+ return C_OK;
+}
+
+Status EnsemblePatchApplication::PredictTransformParameters(
+ SinkStreamSet* all_predicted_parameters) {
+ for (size_t i = 0; i < patchers_.size(); ++i) {
+ SinkStreamSet single_predicted_parameters;
+ Status status =
+ patchers_[i]->PredictTransformParameters(&single_predicted_parameters);
+ if (status != C_OK)
+ return status;
+ if (!all_predicted_parameters->WriteSet(&single_predicted_parameters))
+ return C_STREAM_ERROR;
+ }
+ return C_OK;
+}
+
+Status EnsemblePatchApplication::SubpatchTransformParameters(
+ SinkStreamSet* predicted_parameters,
+ SourceStream* correction,
+ SourceStreamSet* corrected_parameters) {
+ return SubpatchStreamSets(predicted_parameters,
+ correction,
+ corrected_parameters,
+ &corrected_parameters_storage_);
+}
+
+Status EnsemblePatchApplication::TransformUp(
+ SourceStreamSet* parameters,
+ SinkStreamSet* transformed_elements) {
+ for (size_t i = 0; i < patchers_.size(); ++i) {
+ SourceStreamSet single_parameters;
+ if (!parameters->ReadSet(&single_parameters))
+ return C_STREAM_ERROR;
+ SinkStreamSet single_transformed_element;
+ Status status = patchers_[i]->Transform(&single_parameters,
+ &single_transformed_element);
+ if (status != C_OK)
+ return status;
+ if (!single_parameters.Empty())
+ return C_STREAM_NOT_CONSUMED;
+ if (!transformed_elements->WriteSet(&single_transformed_element))
+ return C_STREAM_ERROR;
+ }
+
+ if (!parameters->Empty())
+ return C_STREAM_NOT_CONSUMED;
+ return C_OK;
+}
+
+Status EnsemblePatchApplication::SubpatchTransformedElements(
+ SinkStreamSet* predicted_elements,
+ SourceStream* correction,
+ SourceStreamSet* corrected_elements) {
+ return SubpatchStreamSets(predicted_elements,
+ correction,
+ corrected_elements,
+ &corrected_elements_storage_);
+}
+
+Status EnsemblePatchApplication::TransformDown(
+ SourceStreamSet* transformed_elements,
+ SinkStream* basic_elements) {
+ // Construct blob of original input followed by reformed elements.
+
+ // The original input:
+ basic_elements->Write(base_region_.start(), base_region_.length());
+
+ for (size_t i = 0; i < patchers_.size(); ++i) {
+ SourceStreamSet single_corrected_element;
+ if (!transformed_elements->ReadSet(&single_corrected_element))
+ return C_STREAM_ERROR;
+ Status status = patchers_[i]->Reform(&single_corrected_element,
+ basic_elements);
+ if (status != C_OK)
+ return status;
+ if (!single_corrected_element.Empty())
+ return C_STREAM_NOT_CONSUMED;
+ }
+
+ if (!transformed_elements->Empty())
+ return C_STREAM_NOT_CONSUMED;
+
+ return C_OK;
+}
+
+Status EnsemblePatchApplication::SubpatchFinalOutput(
+ SourceStream* original,
+ SourceStream* correction,
+ SinkStream* corrected_ensemble) {
+ Status delta_status = ApplySimpleDelta(original, correction,
+ corrected_ensemble);
+ if (delta_status != C_OK)
+ return delta_status;
+
+ if (CalculateCrc(corrected_ensemble->Buffer(),
+ corrected_ensemble->Length()) != target_checksum_)
+ return C_BAD_ENSEMBLE_CRC;
+
+ return C_OK;
+}
+
+Status EnsemblePatchApplication::SubpatchStreamSets(
+ SinkStreamSet* predicted_items,
+ SourceStream* correction,
+ SourceStreamSet* corrected_items,
+ SinkStream* corrected_items_storage) {
+ SinkStream linearized_predicted_items;
+ if (!predicted_items->CopyTo(&linearized_predicted_items))
+ return C_STREAM_ERROR;
+
+ SourceStream prediction;
+ prediction.Init(linearized_predicted_items);
+
+ Status status = ApplySimpleDelta(&prediction,
+ correction,
+ corrected_items_storage);
+ if (status != C_OK)
+ return status;
+
+ if (!corrected_items->Init(corrected_items_storage->Buffer(),
+ corrected_items_storage->Length()))
+ return C_STREAM_ERROR;
+
+ return C_OK;
+}
+
+Status ApplyEnsemblePatch(SourceStream* base,
+ SourceStream* patch,
+ SinkStream* output) {
+ Status status;
+ EnsemblePatchApplication patch_process;
+
+ status = patch_process.ReadHeader(patch);
+ if (status != C_OK)
+ return status;
+
+ status = patch_process.InitBase(Region(base->Buffer(), base->Remaining()));
+ if (status != C_OK)
+ return status;
+
+ status = patch_process.ValidateBase();
+ if (status != C_OK)
+ return status;
+
+ // The rest of the patch stream is a StreamSet.
+ SourceStreamSet patch_streams;
+ patch_streams.Init(patch);
+
+ SourceStream* transformation_descriptions = patch_streams.stream(0);
+ SourceStream* parameter_correction = patch_streams.stream(1);
+ SourceStream* transformed_elements_correction = patch_streams.stream(2);
+ SourceStream* ensemble_correction = patch_streams.stream(3);
+
+ status = patch_process.ReadInitialParameters(transformation_descriptions);
+ if (status != C_OK)
+ return status;
+
+ SinkStreamSet predicted_parameters;
+ status = patch_process.PredictTransformParameters(&predicted_parameters);
+ if (status != C_OK)
+ return status;
+
+ SourceStreamSet corrected_parameters;
+ status = patch_process.SubpatchTransformParameters(&predicted_parameters,
+ parameter_correction,
+ &corrected_parameters);
+ if (status != C_OK)
+ return status;
+
+ SinkStreamSet transformed_elements;
+ status = patch_process.TransformUp(&corrected_parameters,
+ &transformed_elements);
+ if (status != C_OK)
+ return status;
+
+ SourceStreamSet corrected_transformed_elements;
+ status = patch_process.SubpatchTransformedElements(
+ &transformed_elements,
+ transformed_elements_correction,
+ &corrected_transformed_elements);
+ if (status != C_OK)
+ return status;
+
+ SinkStream original_ensemble_and_corrected_base_elements;
+ status = patch_process.TransformDown(
+ &corrected_transformed_elements,
+ &original_ensemble_and_corrected_base_elements);
+ if (status != C_OK)
+ return status;
+
+ SourceStream final_patch_prediction;
+ final_patch_prediction.Init(original_ensemble_and_corrected_base_elements);
+ status = patch_process.SubpatchFinalOutput(&final_patch_prediction,
+ ensemble_correction, output);
+ if (status != C_OK)
+ return status;
+
+ return C_OK;
+}
+
+Status ApplyEnsemblePatch(const wchar_t* old_file_name,
+ const wchar_t* patch_file_name,
+ const wchar_t* new_file_name) {
+ Status status;
+
+ // First read enough of the patch file to validate the header is well-formed.
+ // A few varint32 numbers should fit in 100.
+ FilePath patch_file_path(patch_file_name);
+ const int BIG_ENOUGH_FOR_HEADER = 100;
+ char buffer[BIG_ENOUGH_FOR_HEADER];
+ int read_count =
+ file_util::ReadFile(patch_file_path, buffer, sizeof(buffer));
+ if (read_count < 0)
+ return C_READ_OPEN_ERROR;
+
+ // 'Dry-run' the first step of the patch process to validate format of header.
+ SourceStream patch_header_stream;
+ patch_header_stream.Init(buffer, read_count);
+ EnsemblePatchApplication patch_process;
+ status = patch_process.ReadHeader(&patch_header_stream);
+ if (status != C_OK)
+ return status;
+
+ // Header smells good so read the whole patch file for real.
+ std::string patch_file_buffer;
+ if (!file_util::ReadFileToString(patch_file_path, &patch_file_buffer))
+ return C_READ_ERROR;
+
+ // Read the old_file.
+ FilePath old_file_path(old_file_name);
+ std::string old_file_buffer;
+ if (!file_util::ReadFileToString(old_file_path, &old_file_buffer))
+ return C_READ_ERROR;
+
+ // Apply patch on streams.
+ SourceStream old_source_stream;
+ SourceStream patch_source_stream;
+ old_source_stream.Init(old_file_buffer);
+ patch_source_stream.Init(patch_file_buffer);
+ SinkStream new_sink_stream;
+ status = ApplyEnsemblePatch(&old_source_stream, &patch_source_stream,
+ &new_sink_stream);
+
+ // Write the patched data to |new_file_name|.
+ FilePath new_file_path(new_file_name);
+ int written =
+ file_util::WriteFile(
+ new_file_path,
+ reinterpret_cast<const char*>(new_sink_stream.Buffer()),
+ new_sink_stream.Length());
+ if (written == -1)
+ return C_WRITE_OPEN_ERROR;
+ if (written != new_sink_stream.Length())
+ return C_WRITE_ERROR;
+
+ return C_OK;
+}
+
+} // namespace
diff --git a/third_party/courgette/ensemble_create.cc b/third_party/courgette/ensemble_create.cc new file mode 100644 index 0000000..4d64f1c --- /dev/null +++ b/third_party/courgette/ensemble_create.cc @@ -0,0 +1,382 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// The main idea in Courgette is to do patching *under a tranformation*. The
+// input is transformed into a new representation, patching occurs in the new
+// repesentation, and then the tranform is reversed to get the patched data.
+//
+// The idea is applied to pieces (or 'elements') of the whole (or 'ensemble').
+// Each of the elements has to go through the same set of steps in lock-step.
+
+// This file contains the code to create the patch.
+
+
+#include "third_party/courgette/ensemble.h"
+
+#include <vector>
+#include <limits>
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+#include "base/time.h"
+
+#include "third_party/courgette/bsdiff.h"
+#include "third_party/courgette/crc.h"
+#include "third_party/courgette/difference_estimator.h"
+#include "third_party/courgette/image_info.h"
+#include "third_party/courgette/streams.h"
+#include "third_party/courgette/region.h"
+#include "third_party/courgette/simple_delta.h"
+
+#include "third_party/courgette/win32_x86_patcher.h"
+#include "third_party/courgette/win32_x86_generator.h"
+
+namespace courgette {
+
+TransformationPatchGenerator::TransformationPatchGenerator(
+ Element* old_element,
+ Element* new_element,
+ TransformationPatcher* patcher)
+ : old_element_(old_element),
+ new_element_(new_element),
+ patcher_(patcher) {
+}
+
+TransformationPatchGenerator::~TransformationPatchGenerator() {
+ delete patcher_;
+}
+
+// The default implementation of PredictTransformParameters delegates to the
+// patcher.
+Status TransformationPatchGenerator::PredictTransformParameters(
+ SinkStreamSet* prediction) {
+ return patcher_->PredictTransformParameters(prediction);
+}
+
+// The default implementation of Reform delegates to the patcher.
+Status TransformationPatchGenerator::Reform(
+ SourceStreamSet* transformed_element,
+ SinkStream* reformed_element) {
+ return patcher_->Reform(transformed_element, reformed_element);
+}
+
+// Makes a TransformationPatchGenerator of the appropriate variety for the
+// Element kind.
+TransformationPatchGenerator* MakeGenerator(Element* old_element,
+ Element* new_element) {
+ if (new_element->kind() == Element::WIN32_X86_WITH_CODE) {
+ CourgetteWin32X86PatchGenerator* generator =
+ new CourgetteWin32X86PatchGenerator(
+ old_element,
+ new_element,
+ new CourgetteWin32X86Patcher(old_element->region()));
+ return generator;
+ } else {
+ LOG(WARNING) << "Unexpected Element::Kind " << old_element->kind();
+ return NULL;
+ }
+}
+
+// FindGenerators finds TransformationPatchGenerators for the elements of
+// |new_ensemble|. For each element of |new_ensemble| we find the closest
+// matching element from |old_ensemble| and use that as the basis for
+// differential compression. The elements have to be the same kind so as to
+// support transformation into the same kind of 'new representation'.
+//
+Status FindGenerators(Ensemble* old_ensemble, Ensemble* new_ensemble,
+ std::vector<TransformationPatchGenerator*>* generators) {
+ base::Time start_find_time = base::Time::Now();
+ old_ensemble->FindEmbeddedElements();
+ new_ensemble->FindEmbeddedElements();
+ LOG(INFO) << "done FindEmbeddedElements "
+ << (base::Time::Now() - start_find_time).InSecondsF();
+
+ std::vector<Element*> old_elements(old_ensemble->elements());
+ std::vector<Element*> new_elements(new_ensemble->elements());
+
+ LOG(INFO) << "old has " << old_elements.size() << " elements";
+ LOG(INFO) << "new has " << new_elements.size() << " elements";
+
+ DifferenceEstimator difference_estimator;
+ std::vector<DifferenceEstimator::Base*> bases;
+
+ base::Time start_bases_time = base::Time::Now();
+ for (size_t i = 0; i < old_elements.size(); ++i) {
+ bases.push_back(
+ difference_estimator.MakeBase(old_elements[i]->region()));
+ }
+ LOG(INFO) << "done make bases "
+ << (base::Time::Now() - start_bases_time).InSecondsF()
+ << "s";
+
+ for (size_t new_index = 0; new_index < new_elements.size(); ++new_index) {
+ Element* new_element = new_elements[new_index];
+ DifferenceEstimator::Subject* new_subject =
+ difference_estimator.MakeSubject(new_element->region());
+
+ // Search through old elements to find the best match.
+ //
+ // TODO(sra): This is O(N x M), i.e. O(N^2) since old_ensemble and
+ // new_ensemble probably have a very similar structure. We can make the
+ // search faster by making the comparison provided by DifferenceEstimator
+ // more nuanced, returning early if the measured difference is greater than
+ // the current best. This will be most effective if we can arrange that the
+ // first elements we try to match are likely the 'right' ones. We could
+ // prioritize elements that are of a similar size or similar position in the
+ // sequence of elements.
+ //
+ Element* best_old_element = NULL;
+ size_t best_difference = std::numeric_limits<size_t>::max();
+ for (size_t old_index = 0; old_index < old_elements.size(); ++old_index) {
+ Element* old_element = old_elements[old_index];
+ // Elements of different kinds are incompatible.
+ if (old_element->kind() != new_element->kind())
+ continue;
+
+ base::Time start_compare = base::Time::Now();
+ DifferenceEstimator::Base* old_base = bases[old_index];
+ size_t difference = difference_estimator.Measure(old_base, new_subject);
+
+ LOG(INFO) << "Compare " << old_element->Name()
+ << " to " << new_element->Name()
+ << " --> " << difference
+ << " in " << (base::Time::Now() - start_compare).InSecondsF()
+ << "s";
+ if (difference == 0) {
+ LOG(INFO) << "Skip " << new_element->Name()
+ << " - identical to " << old_element->Name();
+ best_difference = 0;
+ best_old_element = NULL;
+ break;
+ }
+ if (difference < best_difference) {
+ best_difference = difference;
+ best_old_element = old_element;
+ }
+ }
+
+ if (best_old_element) {
+ LOG(INFO) << "Matched " << best_old_element->Name()
+ << " to " << new_element->Name()
+ << " --> " << best_difference;
+ TransformationPatchGenerator* generator =
+ MakeGenerator(best_old_element, new_element);
+ if (generator)
+ generators->push_back(generator);
+ }
+ }
+
+ LOG(INFO) << "done FindGenerators "
+ << "found " << generators->size() << " in "
+ << (base::Time::Now() - start_find_time).InSecondsF() << "s";
+
+ return C_OK;
+}
+
+void FreeGenerators(std::vector<TransformationPatchGenerator*>* generators) {
+ for (size_t i = 0; i < generators->size(); ++i) {
+ delete (*generators)[i];
+ }
+ generators->clear();
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+Status GenerateEnsemblePatch(SourceStream* base,
+ SourceStream* update,
+ SinkStream* final_patch) {
+ Region old_region(base->Buffer(), base->Remaining());
+ Region new_region(update->Buffer(), update->Remaining());
+ Ensemble old_ensemble(old_region, "old");
+ Ensemble new_ensemble(new_region, "new");
+ std::vector<TransformationPatchGenerator*> generators;
+ Status generators_status = FindGenerators(&old_ensemble, &new_ensemble,
+ &generators);
+ if (generators_status != C_OK)
+ return generators_status;
+
+ SinkStreamSet patch_streams;
+
+ SinkStream* tranformation_descriptions = patch_streams.stream(0);
+ SinkStream* parameter_correction = patch_streams.stream(1);
+ SinkStream* transformed_elements_correction = patch_streams.stream(2);
+ SinkStream* ensemble_correction = patch_streams.stream(3);
+
+ uint32 number_of_transformations = generators.size();
+ tranformation_descriptions->WriteVarint32(number_of_transformations);
+
+ for (size_t i = 0; i < number_of_transformations; ++i) {
+ CourgettePatchFile::TransformationMethodId kind = generators[i]->Kind();
+ tranformation_descriptions->WriteVarint32(kind);
+ }
+
+ for (size_t i = 0; i < number_of_transformations; ++i) {
+ Status status =
+ generators[i]->WriteInitialParameters(tranformation_descriptions);
+ if (status != C_OK)
+ return status;
+ }
+
+ //
+ // Generate sub-patch for parameters.
+ //
+ SinkStreamSet predicted_parameters_sink;
+ SinkStreamSet corrected_parameters_sink;
+
+ for (size_t i = 0; i < number_of_transformations; ++i) {
+ SinkStreamSet single_predicted_parameters;
+ Status status;
+ status = generators[i]->PredictTransformParameters(
+ &single_predicted_parameters);
+ if (status != C_OK)
+ return status;
+ if (!predicted_parameters_sink.WriteSet(&single_predicted_parameters))
+ return C_STREAM_ERROR;
+
+ SinkStreamSet single_corrected_parameters;
+ status = generators[i]->CorrectedTransformParameters(
+ &single_corrected_parameters);
+ if (status != C_OK)
+ return status;
+ if (!corrected_parameters_sink.WriteSet(&single_corrected_parameters))
+ return C_STREAM_ERROR;
+ }
+
+ SinkStream linearized_predicted_parameters;
+ SinkStream linearized_corrected_parameters;
+
+ if (!predicted_parameters_sink.CopyTo(&linearized_predicted_parameters))
+ return C_STREAM_ERROR;
+ if (!corrected_parameters_sink.CopyTo(&linearized_corrected_parameters))
+ return C_STREAM_ERROR;
+
+ SourceStream predicted_parameters_source;
+ SourceStream corrected_parameters_source;
+ predicted_parameters_source.Init(linearized_predicted_parameters);
+ corrected_parameters_source.Init(linearized_corrected_parameters);
+
+ Status delta1_status = GenerateSimpleDelta(&predicted_parameters_source,
+ &corrected_parameters_source,
+ parameter_correction);
+ if (delta1_status != C_OK)
+ return delta1_status;
+
+ //
+ // Generate sub-patch for elements.
+ //
+ corrected_parameters_source.Init(linearized_corrected_parameters);
+ SourceStreamSet corrected_parameters_source_set;
+ if (!corrected_parameters_source_set.Init(&corrected_parameters_source))
+ return C_STREAM_ERROR;
+
+ SinkStreamSet predicted_transformed_elements;
+ SinkStreamSet corrected_transformed_elements;
+
+ for (size_t i = 0; i < number_of_transformations; ++i) {
+ SourceStreamSet single_parameters;
+ if (!corrected_parameters_source_set.ReadSet(&single_parameters))
+ return C_STREAM_ERROR;
+ SinkStreamSet single_predicted_transformed_element;
+ SinkStreamSet single_corrected_transformed_element;
+ Status status = generators[i]->Transform(
+ &single_parameters,
+ &single_predicted_transformed_element,
+ &single_corrected_transformed_element);
+ if (status != C_OK)
+ return status;
+ if (!single_parameters.Empty())
+ return C_STREAM_NOT_CONSUMED;
+ if (!predicted_transformed_elements.WriteSet(
+ &single_predicted_transformed_element))
+ return C_STREAM_ERROR;
+ if (!corrected_transformed_elements.WriteSet(
+ &single_corrected_transformed_element))
+ return C_STREAM_ERROR;
+ }
+
+ if (!corrected_parameters_source_set.Empty())
+ return C_STREAM_NOT_CONSUMED;
+
+ SinkStream linearized_predicted_transformed_elements;
+ SinkStream linearized_corrected_transformed_elements;
+
+ if (!predicted_transformed_elements.CopyTo(
+ &linearized_predicted_transformed_elements))
+ return C_STREAM_ERROR;
+ if (!corrected_transformed_elements.CopyTo(
+ &linearized_corrected_transformed_elements))
+ return C_STREAM_ERROR;
+
+ SourceStream predicted_transformed_elements_source;
+ SourceStream corrected_transformed_elements_source;
+ predicted_transformed_elements_source
+ .Init(linearized_predicted_transformed_elements);
+ corrected_transformed_elements_source
+ .Init(linearized_corrected_transformed_elements);
+
+ Status delta2_status =
+ GenerateSimpleDelta(&predicted_transformed_elements_source,
+ &corrected_transformed_elements_source,
+ transformed_elements_correction);
+ if (delta2_status != C_OK)
+ return delta2_status;
+
+ //
+ // Generate sub-patch for whole enchilada.
+ //
+ SinkStream predicted_ensemble;
+
+ predicted_ensemble.Write(base->Buffer(), base->Remaining());
+
+ SourceStreamSet corrected_transformed_elements_source_set;
+ corrected_transformed_elements_source
+ .Init(linearized_corrected_transformed_elements);
+ if (!corrected_transformed_elements_source_set
+ .Init(&corrected_transformed_elements_source))
+ return C_STREAM_ERROR;
+
+ for (size_t i = 0; i < number_of_transformations; ++i) {
+ SourceStreamSet single_corrected_transformed_element;
+ if (!corrected_transformed_elements_source_set.ReadSet(
+ &single_corrected_transformed_element))
+ return C_STREAM_ERROR;
+ Status status = generators[i]->Reform(&single_corrected_transformed_element,
+ &predicted_ensemble);
+ if (status != C_OK)
+ return status;
+ if (!single_corrected_transformed_element.Empty())
+ return C_STREAM_NOT_CONSUMED;
+ }
+
+ if (!corrected_transformed_elements_source_set.Empty())
+ return C_STREAM_NOT_CONSUMED;
+
+ FreeGenerators(&generators);
+
+ SourceStream predicted_ensemble_source;
+ predicted_ensemble_source.Init(predicted_ensemble);
+ Status delta3_status = GenerateSimpleDelta(&predicted_ensemble_source,
+ update,
+ ensemble_correction);
+ if (delta3_status != C_OK)
+ return delta3_status;
+
+ //
+ // Final output stream has a header followed by a StreamSet.
+ //
+ final_patch->WriteVarint32(CourgettePatchFile::kMagic);
+ final_patch->WriteVarint32(CourgettePatchFile::kVersion);
+
+ final_patch->WriteVarint32(
+ CalculateCrc(old_region.start(), old_region.length()));
+ final_patch->WriteVarint32(
+ CalculateCrc(new_region.start(), new_region.length()));
+
+ if (!patch_streams.CopyTo(final_patch))
+ return C_STREAM_ERROR;
+
+ return C_OK;
+}
+
+} // namespace
diff --git a/third_party/courgette/image_info.cc b/third_party/courgette/image_info.cc new file mode 100644 index 0000000..ca615dd --- /dev/null +++ b/third_party/courgette/image_info.cc @@ -0,0 +1,392 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "third_party/courgette/image_info.h" + +#include <memory.h> +#include <algorithm> +#include <map> +#include <set> +#include <sstream> +#include <vector> + +#include "base/logging.h" + +namespace courgette { + +std::string SectionName(const Section* section) { + if (section == NULL) + return "<none>"; + char name[9]; + memcpy(name, section->name, 8); + name[8] = '\0'; // Ensure termination. + return name; +} + +PEInfo::PEInfo() + : failure_reason_("uninitialized"), + start_(0), end_(0), length_(0), + is_PE32_plus_(0), file_length_(0), has_text_section_(false) { +} + +void PEInfo::Init(const void* start, size_t length) { + start_ = reinterpret_cast<const uint8*>(start); + length_ = length; + end_ = start_ + length_; + failure_reason_ = "unparsed"; +} + +// DescribeRVA is for debugging only. I would put it under #ifdef DEBUG except +// that during development I'm finding I need to call it when compiled in +// Release mode. Hence: +// TODO(sra): make this compile only for debug mode. +std::string PEInfo::DescribeRVA(RVA rva) const { + const Section* section = RVAToSection(rva); + std::ostringstream s; + s << std::hex << rva; + if (section) { + s << " ("; + s << SectionName(section) << "+" + << std::hex << (rva - section->virtual_address) + << ")"; + } + return s.str(); +} + +const Section* PEInfo::FindNextSection(uint32 fileOffset) const { + const Section* best = 0; + for (int i = 0; i < number_of_sections_; i++) { + const Section* section = §ions_[i]; + if (fileOffset <= section->file_offset_of_raw_data) { + if (best == 0 || + section->file_offset_of_raw_data < best->file_offset_of_raw_data) { + best = section; + } + } + } + return best; +} + +const Section* PEInfo::RVAToSection(RVA rva) const { + for (int i = 0; i < number_of_sections_; i++) { + const Section* section = §ions_[i]; + uint32 offset = rva - section->virtual_address; + if (offset < section->virtual_size) { + return section; + } + } + return NULL; +} + +int PEInfo::RVAToFileOffset(RVA rva) const { + const Section* section = RVAToSection(rva); + if (section) { + uint32 offset = rva - section->virtual_address; + if (offset < section->size_of_raw_data) { + return section->file_offset_of_raw_data + offset; + } else { + return kNoOffset; // In section but not in file (e.g. uninit data). + } + } + + // Small RVA values point into the file header in the loaded image. + // RVA 0 is the module load address which Windows uses as the module handle. + // RVA 2 sometimes occurs, I'm not sure what it is, but it would map into the + // DOS header. + if (rva == 0 || rva == 2) + return rva; + + NOTREACHED(); + return kNoOffset; +} + +const uint8* PEInfo::RVAToPointer(RVA rva) const { + int file_offset = RVAToFileOffset(rva); + if (file_offset == kNoOffset) + return NULL; + else + return start_ + file_offset; +} + +RVA PEInfo::FileOffsetToRVA(uint32 file_offset) const { + for (int i = 0; i < number_of_sections_; i++) { + const Section* section = §ions_[i]; + uint32 offset = file_offset - section->file_offset_of_raw_data; + if (offset < section->size_of_raw_data) { + return section->virtual_address + offset; + } + } + return 0; +} + +//////////////////////////////////////////////////////////////////////////////// + +namespace { + +// Constants and offsets gleaned from WINNT.H and various articles on the +// format of Windows PE executables. + +// This is FIELD_OFFSET(IMAGE_DOS_HEADER, e_lfanew): +const size_t kOffsetOfFileAddressOfNewExeHeader = 0x3c; + +const uint16 kImageNtOptionalHdr32Magic = 0x10b; +const uint16 kImageNtOptionalHdr64Magic = 0x20b; + +const size_t kSizeOfCoffHeader = 20; +const size_t kOffsetOfDataDirectoryFromImageOptionalHeader32 = 96; +const size_t kOffsetOfDataDirectoryFromImageOptionalHeader64 = 112; + +// These helper functions avoid the need for casts in the main code. +inline uint16 ReadU16(const uint8* address, size_t offset) { + return *reinterpret_cast<const uint16*>(address + offset); +} + +inline uint32 ReadU32(const uint8* address, size_t offset) { + return *reinterpret_cast<const uint32*>(address + offset); +} + +inline uint64 ReadU64(const uint8* address, size_t offset) { + return *reinterpret_cast<const uint64*>(address + offset); +} + +} // namespace + +// ParseHeader attempts to match up the buffer with the Windows data +// structures that exist within a Windows 'Portable Executable' format file. +// Returns 'true' if the buffer matches, and 'false' if the data looks +// suspicious. Rather than try to 'map' the buffer to the numerous windows +// structures, we extract the information we need into the courgette::PEInfo +// structure. +// +bool PEInfo::ParseHeader() { + if (length_ < kOffsetOfFileAddressOfNewExeHeader + 4 /*size*/) + return Bad("Too small"); + + // Have 'MZ' magic for a DOS header? + if (start_[0] != 'M' || start_[1] != 'Z') + return Bad("Not MZ"); + + // offset from DOS header to PE header is stored in DOS header. + uint32 offset = ReadU32(start_, kOffsetOfFileAddressOfNewExeHeader); + + const uint8* const pe_header = start_ + offset; + const size_t kMinPEHeaderSize = 4 /*signature*/ + kSizeOfCoffHeader; + if (pe_header <= start_ || pe_header >= end_ - kMinPEHeaderSize) + return Bad("Bad offset to PE header"); + + if (offset % 8 != 0) + return Bad("Misaligned PE header"); + + // The 'PE' header is an IMAGE_NT_HEADERS structure as defined in WINNT.H. + // See http://msdn.microsoft.com/en-us/library/ms680336(VS.85).aspx + // + // The first field of the IMAGE_NT_HEADERS is the signature. + if (!(pe_header[0] == 'P' && + pe_header[1] == 'E' && + pe_header[2] == 0 && + pe_header[3] == 0)) + return Bad("no PE signature"); + + // The second field of the IMAGE_NT_HEADERS is the COFF header. + // The COFF header is also called an IMAGE_FILE_HEADER + // http://msdn.microsoft.com/en-us/library/ms680313(VS.85).aspx + const uint8* const coff_header = pe_header + 4; + machine_type_ = ReadU16(coff_header, 0); + number_of_sections_ = ReadU16(coff_header, 2); + size_of_optional_header_ = ReadU16(coff_header, 16); + + // The rest of the IMAGE_NT_HEADERS is the IMAGE_OPTIONAL_HEADER(32|64) + const uint8* const optional_header = coff_header + kSizeOfCoffHeader; + optional_header_ = optional_header; + + if (optional_header + size_of_optional_header_ >= end_) + return Bad("optional header past end of file"); + + // Check we can read the magic. + if (size_of_optional_header_ < 2) + return Bad("optional header no magic"); + + uint16 magic = ReadU16(optional_header, 0); + + if (magic == kImageNtOptionalHdr32Magic) { + is_PE32_plus_ = false; + offset_of_data_directories_ = + kOffsetOfDataDirectoryFromImageOptionalHeader32; + } else if (magic == kImageNtOptionalHdr64Magic) { + is_PE32_plus_ = true; + offset_of_data_directories_ = + kOffsetOfDataDirectoryFromImageOptionalHeader64; + } else { + return Bad("unrecognized magic"); + } + + // Check that we can read the rest of the the fixed fields. Data directories + // directly follow the fixed fields of the IMAGE_OPTIONAL_HEADER. + if (size_of_optional_header_ < offset_of_data_directories_) + return Bad("optional header too short"); + + // The optional header is either an IMAGE_OPTIONAL_HEADER32 or + // IMAGE_OPTIONAL_HEADER64 + // http://msdn.microsoft.com/en-us/library/ms680339(VS.85).aspx + // + // Copy the fields we care about. + size_of_code_ = ReadU32(optional_header, 4); + size_of_initialized_data_ = ReadU32(optional_header, 8); + size_of_uninitialized_data_ = ReadU32(optional_header, 12); + base_of_code_ = ReadU32(optional_header, 20); + if (is_PE32_plus_) { + base_of_data_ = 0; + image_base_ = ReadU64(optional_header, 24); + } else { + base_of_data_ = ReadU32(optional_header, 24); + image_base_ = ReadU32(optional_header, 28); + } + size_of_image_ = ReadU32(optional_header, 56); + number_of_data_directories_ = + ReadU32(optional_header, (is_PE32_plus_ ? 108 : 92)); + + if (size_of_code_ >= length_ || + size_of_initialized_data_ >= length_ || + size_of_code_ + size_of_initialized_data_ >= length_) { + // This validation fires on some perfectly fine executables. + // return Bad("code or initialized data too big"); + } + + // TODO(sra): we can probably get rid of most of the data directories. + bool b = true; + // 'b &= ...' could be short circuit 'b = b && ...' but it is not necessary + // for correctness and it compiles smaller this way. + b &= ReadDataDirectory(0, &export_table_); + b &= ReadDataDirectory(1, &import_table_); + b &= ReadDataDirectory(2, &resource_table_); + b &= ReadDataDirectory(3, &exception_table_); + b &= ReadDataDirectory(5, &base_relocation_table_); + b &= ReadDataDirectory(11, &bound_import_table_); + b &= ReadDataDirectory(12, &import_address_table_); + b &= ReadDataDirectory(13, &delay_import_descriptor_); + b &= ReadDataDirectory(14, &clr_runtime_header_); + if (!b) { + return Bad("malformed data directory"); + } + + // Sections follow the optional header. + sections_ = + reinterpret_cast<const Section*>(optional_header + + size_of_optional_header_); + file_length_ = 0; + + for (int i = 0; i < number_of_sections_; ++i) { + const Section* section = §ions_[i]; + + // TODO(sra): consider using the 'characteristics' field of the section + // header to see if the section contains instructions. + if (memcmp(section->name, ".text", 6) == 0) + has_text_section_ = true; + + uint32 section_end = + section->file_offset_of_raw_data + section->size_of_raw_data; + if (section_end > file_length_) + file_length_ = section_end; + } + + failure_reason_ = NULL; + return true; +} + +bool PEInfo::ReadDataDirectory(int index, ImageDataDirectory* directory) { + if (index < number_of_data_directories_) { + size_t offset = index * 8 + offset_of_data_directories_; + if (offset >= size_of_optional_header_) + return Bad("number of data directories inconsistent"); + const uint8* data_directory = optional_header_ + offset; + if (data_directory < start_ || data_directory + 8 >= end_) + return Bad("data directory outside image"); + RVA rva = ReadU32(data_directory, 0); + size_t size = ReadU32(data_directory, 4); + if (size > size_of_image_) + return Bad("data directory size too big"); + + // TODO(sra): validate RVA. + directory->address_ = rva; + directory->size_ = size; + return true; + } else { + directory->address_ = 0; + directory->size_ = 0; + return true; + } +} + +bool PEInfo::Bad(const char* reason) { + failure_reason_ = reason; + return false; +} + +//////////////////////////////////////////////////////////////////////////////// + +bool PEInfo::ParseRelocs(std::vector<RVA> *relocs) { + relocs->clear(); + + size_t relocs_size = base_relocation_table_.size_; + if (relocs_size == 0) + return true; + + // The format of the base relocation table is a sequence of variable sized + // IMAGE_BASE_RELOCATION blocks. Search for + // "The format of the base relocation data is somewhat quirky" + // at http://msdn.microsoft.com/en-us/library/ms809762.aspx + + const uint8* start = RVAToPointer(base_relocation_table_.address_); + const uint8* end = start + relocs_size; + + // Make sure entire base relocation table is within the buffer. + if (start < start_ || + start >= end_ || + end <= start_ || + end > end_) { + return Bad(".relocs outside image"); + } + + const uint8* block = start; + + // Walk the variable sized blocks. + while (block + 8 < end) { + RVA page_rva = ReadU32(block, 0); + uint32 size = ReadU32(block, 4); + if (size < 8 || // Size includes header ... + size % 4 != 0) // ... and is word aligned. + return Bad("unreasonable relocs block"); + + const uint8* end_entries = block + size; + + if (end_entries <= block || end_entries <= start_ || end_entries > end_) + return Bad(".relocs block outside image"); + + // Walk through the two-byte entries. + for (const uint8* p = block + 8; p < end_entries; p += 2) { + uint16 entry = ReadU16(p, 0); + int type = entry >> 12; + int offset = entry & 0xFFF; + + RVA rva = page_rva + offset; + if (type == 3) { // IMAGE_REL_BASED_HIGHLOW + relocs->push_back(rva); + } else if (type == 0) { // IMAGE_REL_BASED_ABSOLUTE + // Ignore, used as padding. + } else { + // Does not occur in Windows x86 executables. + return Bad("unknown type of reloc"); + } + } + + block += size; + } + + std::sort(relocs->begin(), relocs->end()); + + return true; +} + +} // namespace courgette + diff --git a/third_party/courgette/image_info.h b/third_party/courgette/image_info.h new file mode 100644 index 0000000..ffdbe97 --- /dev/null +++ b/third_party/courgette/image_info.h @@ -0,0 +1,200 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef COURGETTE_IMAGE_INFO_H_ +#define COURGETTE_IMAGE_INFO_H_ + +#include <string> +#include <vector> + +#include "base/basictypes.h" + +namespace courgette { + +// A Relative Virtual Address is the address in the image file after it is +// loaded into memory relative to the image load address. +typedef uint32 RVA; + +// PE file section header. This struct has the same layout as the +// IMAGE_SECTION_HEADER structure from WINNT.H +// http://msdn.microsoft.com/en-us/library/ms680341(VS.85).aspx +// +#pragma pack(push, 1) // Supported by MSVC and GCC. Ensures no gaps in packing. +struct Section { + char name[8]; + uint32 virtual_size; + uint32 virtual_address; + uint32 size_of_raw_data; + uint32 file_offset_of_raw_data; + uint32 pointer_to_relocations; // Always zero in an image. + uint32 pointer_to_line_numbers; // Always zero in an image. + uint16 number_of_relocations; // Always zero in an image. + uint16 number_of_line_numbers; // Always zero in an image. + uint32 characteristics; +}; +#pragma pack(pop) + +COMPILE_ASSERT(sizeof(Section) == 40, section_is_40_bytes); + +// Returns the name of a section, solving the problem that the name is not +// always properly NUL-terminated. Used only for debugging. +std::string SectionName(const Section* section); + +// ImageDataDirectory has same layout as IMAGE_DATA_DIRECTORY structure from +// WINNT.H +// http://msdn.microsoft.com/en-us/library/ms680305(VS.85).aspx +// +class ImageDataDirectory { + public: + ImageDataDirectory() : address_(0), size_(0) {} + RVA address_; + uint32 size_; +}; + +COMPILE_ASSERT(sizeof(ImageDataDirectory) == 8, + image_data_directory_is_8_bytes); + +// +// PEInfo holds information about a single Windows 'Portable Executable' format +// file in the on-disk format. +// +// Imagine you had concatenated a bunch of 'original' files into one 'big' +// file and read the big file into memory. You could find the executables +// from the original files by calling PEInfo::Init with different addresses. +// If PEInfo::TryParseHeader returns true, then Init was passed the address +// of the first byte of one of the original executables, and PEIinfo::length +// will tell how long the file was. +// +class PEInfo { + public: + PEInfo(); + + // ok() may always be called but returns 'true' only after ParseHeader + // succeeds. + bool ok() const { return failure_reason_ == NULL; } + + // Initialize with buffer. This just sets up the region of memory that + // potentially contains the bytes from an executable file. The caller + // continues to own 'start'. + void Init(const void* start, size_t length); + + // Returns 'true' if the buffer appears to point to a Windows 32 bit + // executable, 'false' otherwise. If ParseHeader() succeeds, other member + // functions may be called. + bool ParseHeader(); + + // Returns 'true' if the base relocation table can be parsed. + // Output is a vector of the RVAs corresponding to locations within executable + // that are listed in the base relocation table. + bool ParseRelocs(std::vector<RVA> *addresses); + + // Returns the length of the image. Valid only if ParseHeader succeeded. + uint32 length() const { return file_length_; } + + bool has_text_section() const { return has_text_section_; } + + uint32 size_of_code() const { return size_of_code_; } + + bool is_32bit() const { return !is_PE32_plus_; } + + // Most addresses are represented as 32-bit RVAs. The one address we can't + // do this with is the image base address. 'image_base' is valid only for + // 32-bit executables. 'image_base_64' is valid for 32- and 64-bit executable. + uint32 image_base() const { return static_cast<uint32>(image_base_); } + uint64 image_base_64() const { return image_base_; } + + const ImageDataDirectory& base_relocation_table() const { + return base_relocation_table_; + } + + bool IsValidRVA(RVA rva) const { return rva < size_of_image_; } + + // Returns description of the RVA, e.g. ".text+0x1243". For debugging only. + std::string DescribeRVA(RVA rva) const; + + // Returns a pointer into the memory copy of the file format. + // FileOffsetToPointer(0) returns a pointer to the start of the file format. + const uint8* FileOffsetToPointer(uint32 offset) const { + return start_ + offset; + } + + // Finds the first section at file_offset or above. + const Section* FindNextSection(uint32 file_offset) const; + // Returns Section containing the relative virtual address, or NULL if none. + const Section* RVAToSection(RVA rva) const; + + // There are 2 'coordinate systems' for reasoning about executables. + // FileOffset - the the offset within a single .EXE or .DLL *file*. + // RVA - relative virtual address (offset within *loaded image*) + // FileOffsetToRVA and RVAToFileOffset convert between these representations. + + RVA FileOffsetToRVA(uint32 offset) const; + + static const int kNoOffset = -1; + // Returns kNoOffset if there is no file offset corresponding to 'rva'. + int RVAToFileOffset(RVA rva) const; + + // Returns same as FileOffsetToPointer(RVAToFileOffset(rva)) except that NULL + // is returned if there is no file offset corresponding to 'rva'. + const uint8* RVAToPointer(RVA rva) const; + + protected: + // + // Fields that are always valid. + // + const char* failure_reason_; + + // + // Basic information that is always valid after Init. + // + const uint8* start_; // In current memory, base for 'file offsets'. + const uint8* end_; // In current memory. + unsigned int length_; // In current memory. + + // + // Information that is valid after successful ParseHeader. + // + bool is_PE32_plus_; // PE32_plus is for 64 bit executables. + uint32 file_length_; + + // Location and size of IMAGE_OPTIONAL_HEADER in the buffer. + const uint8 *optional_header_; + uint16 size_of_optional_header_; + uint16 offset_of_data_directories_; + + uint16 machine_type_; + uint16 number_of_sections_; + const Section *sections_; + bool has_text_section_; + + uint32 size_of_code_; + uint32 size_of_initialized_data_; + uint32 size_of_uninitialized_data_; + RVA base_of_code_; + RVA base_of_data_; + + uint64 image_base_; // range limited to 32 bits for 32 bit executable + uint32 size_of_image_; + int number_of_data_directories_; + + ImageDataDirectory export_table_; + ImageDataDirectory import_table_; + ImageDataDirectory resource_table_; + ImageDataDirectory exception_table_; + ImageDataDirectory base_relocation_table_; + ImageDataDirectory bound_import_table_; + ImageDataDirectory import_address_table_; + ImageDataDirectory delay_import_descriptor_; + ImageDataDirectory clr_runtime_header_; + + private: + bool ReadDataDirectory(int index, ImageDataDirectory* dir); + bool Bad(const char *reason); + + DISALLOW_COPY_AND_ASSIGN(PEInfo); +}; + +} // namespace +#endif // COURGETTE_IMAGE_INFO_H_ + diff --git a/third_party/courgette/image_info_unittest.cc b/third_party/courgette/image_info_unittest.cc new file mode 100644 index 0000000..43ef65f --- /dev/null +++ b/third_party/courgette/image_info_unittest.cc @@ -0,0 +1,106 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "third_party/courgette/image_info.h" + +#include <string> + +#include "base/path_service.h" +#include "base/file_util.h" +#include "base/string_util.h" +#include "testing/gtest/include/gtest/gtest.h" + +class ImageInfoTest : public testing::Test { + public: + + void TestExe() const; + void TestResourceDll() const; + + private: + void SetUp() { + PathService::Get(base::DIR_SOURCE_ROOT, &test_dir_); + // file_util::AppendToPath(&test_dir_, L"third_party"); + file_util::AppendToPath(&test_dir_, L"courgette"); + file_util::AppendToPath(&test_dir_, L"testdata"); + } + + void TearDown() { + } + + void ExpectExecutable(courgette::PEInfo *info) const; + + std::string FileContents(const char *file_name) const; + + std::wstring test_dir_; +}; + +// Reads a test file into a string. +std::string ImageInfoTest::FileContents(const char *file_name) const { + std::wstring file_path = test_dir_; + file_util::AppendToPath(&file_path, UTF8ToWide(file_name)); + std::string file_bytes; + if (!file_util::ReadFileToString(file_path, &file_bytes)) { + EXPECT_TRUE(!"Could not read test data"); + } + return file_bytes; +} + +void ImageInfoTest::ExpectExecutable(courgette::PEInfo *info) const { + EXPECT_TRUE(info->ok()); + EXPECT_TRUE(info->has_text_section()); +} + +void ImageInfoTest::TestExe() const { + std::string file1 = FileContents("setup1.exe"); + + courgette::PEInfo *info = new courgette::PEInfo(); + info->Init(reinterpret_cast<const uint8*>(file1.c_str()), file1.length()); + + bool can_parse_header = info->ParseHeader(); + EXPECT_TRUE(can_parse_header); + + // The executable is the whole file, not 'embedded' with the file + EXPECT_EQ(file1.length(), info->length()); + + ExpectExecutable(info); + EXPECT_EQ(449536, info->size_of_code()); + EXPECT_EQ(SectionName(info->RVAToSection(0x00401234 - 0x00400000)), + std::string(".text")); + + EXPECT_EQ(0, info->RVAToFileOffset(0)); + EXPECT_EQ(1024, info->RVAToFileOffset(4096)); + EXPECT_EQ(46928, info->RVAToFileOffset(50000)); + + std::vector<courgette::RVA> relocs; + bool can_parse_relocs = info->ParseRelocs(&relocs); + EXPECT_TRUE(can_parse_relocs); + + const uint8* p = info->RVAToPointer(0); + EXPECT_EQ(reinterpret_cast<const void*>(file1.c_str()), + reinterpret_cast<const void*>(p)); + EXPECT_EQ('M', p[0]); + EXPECT_EQ('Z', p[1]); +} + +void ImageInfoTest::TestResourceDll() const { + std::string file1 = FileContents("en-US.dll"); + + courgette::PEInfo *info = new courgette::PEInfo(); + info->Init(reinterpret_cast<const uint8*>(file1.c_str()), file1.length()); + + bool can_parse_header = info->ParseHeader(); + EXPECT_TRUE(can_parse_header); + + // The executable is the whole file, not 'embedded' with the file + EXPECT_EQ(file1.length(), info->length()); + + EXPECT_TRUE(info->ok()); + EXPECT_FALSE(info->has_text_section()); + EXPECT_EQ(0u, info->size_of_code()); +} + +TEST_F(ImageInfoTest, All) { + TestExe(); + TestResourceDll(); +} diff --git a/third_party/courgette/memory_monitor.cc b/third_party/courgette/memory_monitor.cc new file mode 100644 index 0000000..2077f12 --- /dev/null +++ b/third_party/courgette/memory_monitor.cc @@ -0,0 +1,122 @@ +#include <stdio.h>
+#include <map>
+
+#include "base/logging.h"
+#include "base/string_util.h"
+
+bool inH = true;
+struct H {
+ H() { inH = false; tick_ = 0; bw_ = 0; d_bw_ = d_tick_ = 0; m_bw_ = 0; mem_ = high_ = 0;}
+ ~H() {
+ inH = true;
+ int i = 0;
+ for (M::iterator p = m_.begin(); p != m_.end(); ++p, ++i) {
+ size_t s = p->first;
+ LOG(INFO) << StringPrintf("%3d %8u: %8u %8u %8u %8u", i, s,
+ m_[s], c_[s], h_[s], h_[s] * s);
+ }
+ LOG(INFO) << "Peak " << fmt(high_);
+ }
+
+ std::string fmt(size_t s) {
+ if (s > 1000000000) return StringPrintf("%.3gG", s/(1000000000.0));
+ if (s > 1000000) return StringPrintf("%.3gM", s/(1000000.));
+ if (s > 9999) return StringPrintf("%.3gk", s/(1000.));
+ return StringPrintf("%d", (int)s);
+ }
+
+ void tick(size_t w, char sign) {
+ d_tick_ += 1;
+ d_bw_ += w;
+ const size_t T = 4*4*1024;
+ const size_t M = 4*1024*1024;
+ bool print = false;
+ if (d_tick_ >= T) {
+ tick_ += (d_tick_/T)*T;
+ d_tick_ %= T;
+ print = true;
+ }
+ if (d_bw_ >= M) {
+ bw_ += (d_bw_/M) * M;
+ d_bw_ %= M;
+ print = true;
+ }
+ if (!print) return;
+ std::string o;
+ StringAppendF(&o, "%u:", tick_ + d_tick_);
+ StringAppendF(&o, " (%c%s)", sign, fmt(w).c_str());
+ size_t sum = 0;
+ for (M::iterator p = c_.begin(); p != c_.end(); ++p) {
+ size_t s = p->first;
+ size_t n = p->second;
+ if (n) {
+ if (s*n >= 64*1024)
+ if (n == 1)
+ StringAppendF(&o, " %s", fmt(s).c_str());
+ else
+ StringAppendF(&o, " %s*%u", fmt(s).c_str(), n);
+ sum += s*n;
+ }
+ }
+ StringAppendF(&o, " = %s", fmt(sum).c_str());
+ LOG(INFO) << o;
+ //printf("%s\n", o.c_str());
+ if (sum > 200*1024*1024) {
+ // __asm int 3;
+ m_bw_ = sum;
+ }
+ }
+ void add(size_t s, void *p) {
+ if (!inH) {
+ inH = true;
+ mem_ += s; if (mem_ > high_) high_ = mem_;
+ c_[s] += 1;
+ m_[s] += 1;
+ if (c_[s] > h_[s]) h_[s] = c_[s];
+ allocs_[p] = s;
+ inH = false;
+ tick(s, '+');
+ }
+ }
+
+ void sub(void *p) {
+ if (!inH) {
+ inH = true;
+ size_t s = allocs_[p];
+ if (s) {
+ mem_ -= s;
+ c_[s] -= 1;
+ allocs_[p] = 0;
+ tick(s, '-');
+ }
+ inH = false;
+ }
+ }
+
+ typedef std::map<size_t, size_t> M;
+ M m_;
+ M c_;
+ M h_;
+
+ size_t bw_;
+ size_t d_bw_;
+ size_t tick_;
+ size_t d_tick_;
+ size_t m_bw_;
+ size_t mem_;
+ size_t high_;
+
+ std::map<void*, size_t> allocs_;
+} _H;
+
+void* operator new(size_t s) {
+ //printf("%u\n", s);
+ void *p = malloc(s);
+ _H.add(s, p);
+ return p;
+}
+
+void operator delete(void *p) {
+ _H.sub(p);
+ free(p);
+}
diff --git a/third_party/courgette/region.h b/third_party/courgette/region.h new file mode 100644 index 0000000..00a130f --- /dev/null +++ b/third_party/courgette/region.h @@ -0,0 +1,62 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef COURGETTE_REGION_H_
+#define COURGETTE_REGION_H_
+
+#include <string>
+
+#include "base/basictypes.h"
+
+namespace courgette {
+
+// A Region is a descriptor for a region of memory. It has a start address and
+// a length measured in bytes. The Region object does not own the memory.
+//
+class Region {
+ public:
+ // Default constructor: and empty region.
+ Region() : start_(NULL), length_(0) {}
+
+ // Usual constructor for regions given a |start| address and |length|.
+ Region(const void* start, size_t length)
+ : start_(static_cast<const uint8*>(start)),
+ length_(length) {
+ }
+
+ // String constructor. Region is owned by the string, so the string should
+ // have a lifetime greater than the region.
+ explicit Region(const std::string& string)
+ : start_(reinterpret_cast<const uint8*>(string.c_str())),
+ length_(string.length()) {
+ }
+
+ // Copy constructor.
+ Region(const Region& other) : start_(other.start_), length_(other.length_) {}
+
+ // Assignment 'operator' makes |this| region the same as |other|.
+ Region& assign(const Region& other) {
+ this->start_ = other.start_;
+ this->length_ = other.length_;
+ return *this;
+ }
+
+ // Returns the starting address of the region.
+ const uint8* start() const { return start_; }
+
+ // Returns the length of the region.
+ size_t length() const { return length_; }
+
+ // Returns the address after the last byte of the region.
+ const uint8* end() const { return start_ + length_; }
+
+ private:
+ const uint8* start_;
+ size_t length_;
+
+ void operator=(const Region&); // Disallow assignment operator.
+};
+
+} // namespace
+#endif // COURGETTE_REGION_H_
diff --git a/third_party/courgette/run_all_unittests.cc b/third_party/courgette/run_all_unittests.cc new file mode 100644 index 0000000..5a17ba1 --- /dev/null +++ b/third_party/courgette/run_all_unittests.cc @@ -0,0 +1,10 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/test_suite.h"
+
+int main(int argc, char** argv) {
+ return TestSuite(argc, argv).Run();
+}
+
diff --git a/third_party/courgette/simple_delta.cc b/third_party/courgette/simple_delta.cc new file mode 100644 index 0000000..8f93095 --- /dev/null +++ b/third_party/courgette/simple_delta.cc @@ -0,0 +1,41 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Implementation of the byte-level differential compression used internally by
+// Courgette.
+
+#include "third_party/courgette/simple_delta.h"
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+
+#include "third_party/courgette/bsdiff.h"
+
+namespace courgette {
+
+namespace {
+
+Status BSDiffStatusToStatus(BSDiffStatus status) {
+ switch (status) {
+ case OK: return C_OK;
+ case CRC_ERROR: return C_BINARY_DIFF_CRC_ERROR;
+ default: return C_GENERAL_ERROR;
+ }
+}
+
+}
+
+Status ApplySimpleDelta(SourceStream* old, SourceStream* delta,
+ SinkStream* target) {
+ return BSDiffStatusToStatus(ApplyBinaryPatch(old, delta, target));
+}
+
+Status GenerateSimpleDelta(SourceStream* old, SourceStream* target,
+ SinkStream* delta) {
+ LOG(INFO) << "GenerateSimpleDelta "
+ << old->Remaining() << " " << target->Remaining();
+ return BSDiffStatusToStatus(CreateBinaryPatch(old, target, delta));
+}
+
+} // namespace courgette
diff --git a/third_party/courgette/simple_delta.h b/third_party/courgette/simple_delta.h new file mode 100644 index 0000000..acb2227 --- /dev/null +++ b/third_party/courgette/simple_delta.h @@ -0,0 +1,23 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Byte level differential compression algorithm used by Courgette.
+
+#ifndef COURGETTE_SIMPLE_DELTA_H_
+#define COURGETTE_SIMPLE_DELTA_H_
+
+#include "third_party/courgette/courgette.h"
+#include "third_party/courgette/streams.h"
+
+namespace courgette {
+
+Status ApplySimpleDelta(SourceStream* old, SourceStream* delta,
+ SinkStream* target);
+
+Status GenerateSimpleDelta(SourceStream* old, SourceStream* target,
+ SinkStream* delta);
+
+} // namespace courgette
+
+#endif // COURGETTE_SIMPLE_DELTA_H_
diff --git a/third_party/courgette/streams.cc b/third_party/courgette/streams.cc new file mode 100644 index 0000000..9870cd2 --- /dev/null +++ b/third_party/courgette/streams.cc @@ -0,0 +1,383 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +// Streams classes. +// +// These memory-resident streams are used for serializing data into a sequential +// region of memory. +// +// Streams are divided into SourceStreams for reading and SinkStreams for +// writing. Streams are aggregated into Sets which allows several streams to be +// used at once. Example: we can write A1, B1, A2, B2 but achieve the memory +// layout A1 A2 B1 B2 by writing 'A's to one stream and 'B's to another. +// +// The aggregated streams are important to Courgette's compression efficiency, +// we use it to cluster similar kinds of data which helps to generate longer +// common subsequences and repeated sequences. + +#include "third_party/courgette/streams.h" + +#include <io.h> +#include <memory.h> + +#include "base/basictypes.h" + +namespace courgette { + +// Update this version number if the serialization format of a StreamSet +// changes. +static const unsigned int kStreamsSerializationFormatVersion = 20090218; + +// +// This is a cut down Varint implementation, implementing only what we use for +// streams. The original implementation is at google3/util/coding/varint.h +// +class Varint { + public: + // Maximum lengths of varint encoding of uint32 + static const int kMax32 = 5; + + // Parses a Varint32 encoded value from |source| and stores it in |output|, + // and returns a pointer to the following byte. Returns NULL if a valid + // varint value was not found before |limit|. + static const uint8* Parse32WithLimit(const uint8* source, const uint8* limit, + uint32* output); + + // Writes the Varint32 encoded representation of |value| to buffer + // |destination|. |destination| must have sufficient length to hold kMax32 + // bytes. Returns a pointer to the byte just past the last encoded byte. + static uint8* Encode32(uint8* destination, uint32 value); +}; + +// Parses a Varint32 encoded unsigned number from |source|. The Varint32 +// encoding is a little-endian sequence of bytes containing base-128 digits, +// with the high order bit set to indicate if there are more digits. +// +// For each byte, we mask out the digit and 'or' it into the right place in the +// result. +// +// The digit loop is unrolled for performance. It usually exits after the first +// one or two digits. +const uint8* Varint::Parse32WithLimit(const uint8* source, + const uint8* limit, + uint32* output) { + uint32 digit, result; + if (source >= limit) + return NULL; + digit = *(source++); + result = digit & 127; + if (digit < 128) { + *output = result; + return source; + } + + if (source >= limit) + return NULL; + digit = *(source++); + result |= (digit & 127) << 7; + if (digit < 128) { + *output = result; + return source; + } + + if (source >= limit) + return NULL; + digit = *(source++); + result |= (digit & 127) << 14; + if (digit < 128) { + *output = result; + return source; + } + + if (source >= limit) + return NULL; + digit = *(source++); + result |= (digit & 127) << 21; + if (digit < 128) { + *output = result; + return source; + } + + if (source >= limit) + return NULL; + digit = *(source++); + result |= (digit & 127) << 28; + if (digit < 128) { + *output = result; + return source; + } + + return NULL; // Value is too long to be a Varint32. +} + +// Write the base-128 digits in little-endian order. All except the last digit +// have the high bit set to indicate more digits. +inline uint8* Varint::Encode32(uint8* destination, uint32 value) { + while (value >= 128) { + *(destination++) = value | 128; + value = value >> 7; + } + *(destination++) = value; + return destination; +} + +void SourceStream::Init(const SinkStream& sink) { + Init(sink.Buffer(), sink.Length()); +} + +bool SourceStream::Read(void* destination, size_t count) { + if (current_ + count > end_) + return false; + memcpy(destination, current_, count); + current_ += count; + return true; +} + +bool SourceStream::ReadVarint32(uint32* output_value) { + const uint8* after = Varint::Parse32WithLimit(current_, end_, output_value); + if (!after) + return false; + current_ = after; + return true; +} + +bool SourceStream::ReadVarint32Signed(int32* output_value) { + // Signed numbers are encoded as unsigned numbers so that numbers nearer zero + // have shorter varint encoding. + // 0000xxxx encoded as 000xxxx0. + // 1111xxxx encoded as 000yyyy1 where yyyy is complement of xxxx. + uint32 unsigned_value; + if (!ReadVarint32(&unsigned_value)) + return false; + if (unsigned_value & 1) + *output_value = ~static_cast<int32>(unsigned_value >> 1); + else + *output_value = (unsigned_value >> 1); + return true; +} + +bool SourceStream::ShareSubstream(size_t offset, size_t length, + SourceStream* substream) { + if (offset > Remaining()) + return false; + if (length > Remaining() - offset) + return false; + substream->Init(current_ + offset, length); + return true; +} + +bool SourceStream::ReadSubstream(size_t length, SourceStream* substream) { + if (!ShareSubstream(0, length, substream)) + return false; + current_ += length; + return true; +} + +bool SourceStream::Skip(size_t byte_count) { + if (current_ + byte_count > end_) + return false; + current_ += byte_count; + return true; +} + +void SinkStream::Write(const void* data, size_t byte_count) { + buffer_.append(static_cast<const char*>(data), byte_count); +} + +void SinkStream::WriteVarint32(uint32 value) { + uint8 buffer[Varint::kMax32]; + uint8* end = Varint::Encode32(buffer, value); + Write(buffer, end - buffer); +} + +void SinkStream::WriteVarint32Signed(int32 value) { + // Encode signed numbers so that numbers nearer zero have shorter + // varint encoding. + // 0000xxxx encoded as 000xxxx0. + // 1111xxxx encoded as 000yyyy1 where yyyy is complement of xxxx. + if (value < 0) + WriteVarint32(~value * 2 + 1); + else + WriteVarint32(value * 2); +} + +void SinkStream::Append(SinkStream* other) { + Write(other->buffer_.c_str(), other->buffer_.size()); + other->buffer_.clear(); + other->buffer_.reserve(0); // Non-binding request to reduce storage. +} + +//////////////////////////////////////////////////////////////////////////////// + +SourceStreamSet::SourceStreamSet() + : count_(kMaxStreams) { +} + +SourceStreamSet::~SourceStreamSet() { +} + + +// Initializes from |source|. +// The stream set for N streams is serialized as a header +// <version><N><length1><length2>...<lengthN> +// followed by the stream contents +// <bytes1><bytes2>...<bytesN> +// +bool SourceStreamSet::Init(const void* source, size_t byte_count) { + const uint8* start = static_cast<const uint8*>(source); + const uint8* end = start + byte_count; + + unsigned int version; + const uint8* finger = Varint::Parse32WithLimit(start, end, &version); + if (finger == NULL) + return false; + if (version != kStreamsSerializationFormatVersion) + return false; + + unsigned int count; + finger = Varint::Parse32WithLimit(finger, end, &count); + if (finger == NULL) + return false; + if (count > kMaxStreams) + return false; + + count_ = count; + + unsigned int lengths[kMaxStreams]; + size_t accumulated_length = 0; + + for (size_t i = 0; i < count_; ++i) { + finger = Varint::Parse32WithLimit(finger, end, &lengths[i]); + if (finger == NULL) + return false; + accumulated_length += lengths[i]; + } + + // Remaining bytes should add up to sum of lengths. + if (end - finger != accumulated_length) + return false; + + accumulated_length = finger - start; + for (size_t i = 0; i < count_; ++i) { + stream(i)->Init(start + accumulated_length, lengths[i]); + accumulated_length += lengths[i]; + } + + return true; +} + +bool SourceStreamSet::Init(SourceStream* source) { + // TODO(sra): consume the rest of |source|. + return Init(source->Buffer(), source->Remaining()); +} + +bool SourceStreamSet::ReadSet(SourceStreamSet* set) { + uint32 stream_count = 0; + SourceStream* control_stream = this->stream(0); + if (!control_stream->ReadVarint32(&stream_count)) + return false; + + uint32 lengths[kMaxStreams] = {}; // i.e. all zero. + + for (size_t i = 0; i < stream_count; ++i) { + if (!control_stream->ReadVarint32(&lengths[i])) + return false; + } + + for (size_t i = 0; i < stream_count; ++i) { + if (!this->stream(i)->ReadSubstream(lengths[i], set->stream(i))) + return false; + } + return true; +} + +bool SourceStreamSet::Empty() const { + for (size_t i = 0; i < count_; ++i) { + if (streams_[i].Remaining() != 0) + return false; + } + return true; +} + +//////////////////////////////////////////////////////////////////////////////// + +SinkStreamSet::SinkStreamSet() + : count_(kMaxStreams) { +} + +SinkStreamSet::~SinkStreamSet() { +} + +void SinkStreamSet::Init(size_t stream_index_limit) { + count_ = stream_index_limit; +} + +// The header for a stream set for N streams is serialized as +// <version><N><length1><length2>...<lengthN> +void SinkStreamSet::CopyHeaderTo(SinkStream* header) { + header->WriteVarint32(kStreamsSerializationFormatVersion); + header->WriteVarint32(count_); + for (size_t i = 0; i < count_; ++i) { + header->WriteVarint32(stream(i)->Length()); + } +} + +// Writes |this| to |combined_stream|. See SourceStreamSet::Init for the layout +// of the stream metadata and contents. +bool SinkStreamSet::CopyTo(SinkStream *combined_stream) { + SinkStream header; + CopyHeaderTo(&header); + combined_stream->Append(&header); + for (size_t i = 0; i < count_; ++i) { + combined_stream->Append(stream(i)); + } + return true; +} + +namespace { +bool Write(int file_descriptor, SinkStream* sink) { + size_t length = sink->Length(); + const void *buffer = sink->Buffer(); + int bytes_written = _write(file_descriptor, buffer, length); + return bytes_written == length; +} +} + +bool SinkStreamSet::CopyToFileDescriptor(int file_descriptor) { + SinkStream header; + CopyHeaderTo(&header); + if (!Write(file_descriptor, &header)) + return false; + for (size_t i = 0; i < count_; ++i) { + if (!Write(file_descriptor, stream(i))) + return false; + } + return true; +} + +bool SinkStreamSet::WriteSet(SinkStreamSet* set) { + uint32 lengths[kMaxStreams]; + // 'stream_count' includes all non-empty streams and all empty stream numbered + // lower than a non-empty stream. + size_t stream_count = 0; + for (size_t i = 0; i < kMaxStreams; ++i) { + SinkStream* stream = set->stream(i); + lengths[i] = stream->Length(); + if (lengths[i] > 0) + stream_count = i + 1; + } + + SinkStream* control_stream = this->stream(0); + control_stream->WriteVarint32(stream_count); + for (size_t i = 0; i < stream_count; ++i) { + control_stream->WriteVarint32(lengths[i]); + } + + for (size_t i = 0; i < stream_count; ++i) { + this->stream(i)->Append(set->stream(i)); + } + return true; +} + +} // namespace diff --git a/third_party/courgette/streams.h b/third_party/courgette/streams.h new file mode 100644 index 0000000..4985310 --- /dev/null +++ b/third_party/courgette/streams.h @@ -0,0 +1,220 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +// Streams classes. +// +// These memory-resident streams are used for serialzing data into a sequential +// region of memory. +// Streams are divided into SourceStreams for reading and SinkStreams for +// writing. Streams are aggregated into Sets which allows several streams to be +// used at once. Example: we can write A1, B1, A2, B2 but achive the memory +// layout A1 A2 B1 B2 by writing 'A's to one stream and 'B's to another. +#ifndef COURGETTE_STREAMS_H_ +#define COURGETTE_STREAMS_H_ + +#include <stdio.h> // for FILE* +#include <string> + +#include "base/basictypes.h" + +#include "third_party/courgette/region.h" + +namespace courgette { + +class SourceStream; +class SinkStream; + +// Maximum number of streams in a stream set. +static const unsigned int kMaxStreams = 10; + +// A SourceStream allows a region of memory to be scanned by a sequence of Read +// operations. The stream does not own the memory. +class SourceStream { + public: + SourceStream() : start_(NULL), end_(NULL), current_(NULL) {} + + // Initializes the SourceStream to yield the bytes at |pointer|. The caller + // still owns the memory at |pointer| and should free the memory only after + // the last use of the stream. + void Init(const void* pointer, size_t length) { + start_ = static_cast<const uint8*>(pointer); + end_ = start_ + length; + current_ = start_; + } + + // Initializes the SourceStream to yield the bytes in |region|. The caller + // still owns the memory at |region| and should free the memory only after + // the last use of the stream. + void Init(const Region& region) { Init(region.start(), region.length()); } + + // Initializes the SourceStream to yield the bytes in |string|. The caller + // still owns the memory at |string| and should free the memory only after + // the last use of the stream. + void Init(const std::string& string) { Init(string.c_str(), string.size()); } + + // Initializes the SourceStream to yield the bytes written to |sink|. |sink| + // still owns the memory, so needs to outlive |this|. |sink| should not be + // written to after |this| is initialized. + void Init(const SinkStream& sink); + + // Returns number of bytes remaining to be read from stream. + size_t Remaining() const { return end_ - current_; } + + // Returns initial length of stream before any data consumed by reading. + size_t OriginalLength() const { return end_ - start_; } + + const uint8* Buffer() const { return current_; } + bool Empty() const { return current_ == end_; } + + // Copies bytes from stream to memory at |destination|. Returns 'false' if + // insufficient data to satisfy request. + bool Read(void* destination, size_t byte_count); + + // Reads a varint formatted unsigned integer from stream. Returns 'false' if + // the read failed due to insufficient data or malformed Varint32. + bool ReadVarint32(uint32* output_value); + + // Reads a varint formatted signed integer from stream. Returns 'false' if + // the read failed due to insufficient data or malformed Varint32. + bool ReadVarint32Signed(int32* output_value); + + // Initializes |substream| to yield |length| bytes from |this| stream, + // starting at |offset| bytes from the current position. Returns 'false' if + // there are insufficient bytes in |this| stream. + bool ShareSubstream(size_t offset, size_t length, SourceStream* substream); + + // Initializes |substream| to yield |length| bytes from |this| stream, + // starting at the current position. Returns 'false' if there are + // insufficient bytes in |this| stream. + bool ShareSubstream(size_t length, SourceStream* substream) { + return ShareSubstream(0, length, substream); + } + + // Reads |length| bytes from |this| stream. Initializes |substream| to yield + // the bytes. Returns 'false' if there are insufficient bytes in |this| + // stream. + bool ReadSubstream(size_t length, SourceStream* substream); + + // Skips over bytes. Returns 'false' if insufficient data to satisfy request. + bool Skip(size_t byte_count); + + private: + const uint8* start_; // Points to start of buffer. + const uint8* end_; // Points to first location after buffer. + const uint8* current_; // Points into buffer at current read location. + + DISALLOW_COPY_AND_ASSIGN(SourceStream); +}; + +// A SinkStream accumulates writes into a buffer that it owns. The stream is +// initialy in an 'accumulating' state where writes are permitted. Accessing +// the buffer moves the stream into a 'locked' state where no more writes are +// permitted. The stream may also be in a 'retired' state where the buffer +// contents are no longer available. +class SinkStream { + public: + SinkStream() {} + ~SinkStream() {} + + // Appends |byte_count| bytes from |data| to the stream. + void Write(const void* data, size_t byte_count); + + // Appends the 'varint32' encoding of |value| to the stream. + void WriteVarint32(uint32 value); + + // Appends the 'varint32' encoding of |value| to the stream. + void WriteVarint32Signed(int32 value); + + // Contents of |other| are appended to |this| stream. The |other| stream + // becomes retired. + void Append(SinkStream* other); + + // Returns the number of bytes in this SinkStream + size_t Length() const { return buffer_.size(); } + + // Returns a pointer to contiguously allocated Length() bytes in the stream. + // Writing to the stream invalidates the pointer. The SinkStream continues to + // own the memory. + const uint8* Buffer() const { + return reinterpret_cast<const uint8*>(buffer_.c_str()); + } + + // Hints that the stream will grow by an additional |length| bytes. + void Reserve(size_t length) { buffer_.reserve(length + buffer_.length()); } + + private: + std::string buffer_; // Use a string to manage the stream's memory. + + DISALLOW_COPY_AND_ASSIGN(SinkStream); +}; + +// A SourceStreamSet is a set of SourceStreams. +class SourceStreamSet { + public: + SourceStreamSet(); + ~SourceStreamSet(); + + // Initializes the SourceStreamSet with the stream data in memory at |source|. + // The caller continues to own the memory and should not modify or free the + // memory until the SourceStreamSet destructor has been called. + // + // The layout of the streams are as written by SinkStreamSet::CopyTo. + // Init returns 'false' if the layout is inconsistent with |byte_count|. + bool Init(const void* source, size_t byte_count); + + // Initializes |this| from |source|. The caller continues to own the memory + // because it continues to be owned by |source|. + bool Init(SourceStream* source); + + // Returns a pointer to one of the sub-streams. + SourceStream* stream(size_t id) { return id < count_ ? &streams_[id] : NULL; } + + // Initialize |set| from |this|. + bool ReadSet(SourceStreamSet* set); + + // Returns 'true' if all streams are completely consumed. + bool Empty() const; + + private: + size_t count_; + SourceStream streams_[kMaxStreams]; + + DISALLOW_COPY_AND_ASSIGN(SourceStreamSet); +}; + +class SinkStreamSet { + public: + SinkStreamSet(); + ~SinkStreamSet(); + + // Initializes the SinkStreamSet to have |stream_index_limit| streams. Must + // be <= kMaxStreams. If Init is not called the default is has kMaxStream. + void Init(size_t stream_index_limit); + + // Returns a pointer to a substream. + SinkStream* stream(size_t id) { return id < count_ ? &streams_[id] : NULL; } + + // CopyTo serializes the streams in the SinkStreamSet into a single target + // stream or file. The serialized format may be re-read by initializing a + // SourceStreamSet with a buffer containing the data. + bool CopyTo(SinkStream* combined_stream); + bool CopyToFile(FILE* file); + bool CopyToFileDescriptor(int file_descriptor); + + // Writes the streams of |set| into the corresponding streams of |this|. + // Stream zero first has some metadata written to it. |set| becomes retired. + // Partner to SourceStreamSet::ReadSet. + bool WriteSet(SinkStreamSet* set); + + private: + void CopyHeaderTo(SinkStream* stream); + + size_t count_; + SinkStream streams_[kMaxStreams]; + + DISALLOW_COPY_AND_ASSIGN(SinkStreamSet); +}; + +} // namespace +#endif // COURGETTE_STREAMS_H_ diff --git a/third_party/courgette/streams_unittest.cc b/third_party/courgette/streams_unittest.cc new file mode 100644 index 0000000..90a6061 --- /dev/null +++ b/third_party/courgette/streams_unittest.cc @@ -0,0 +1,200 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "third_party/courgette/streams.h" + +#include "testing/gtest/include/gtest/gtest.h" + +TEST(StreamsTest, SimpleWriteRead) { + const unsigned int kValue1 = 12345; + courgette::SinkStream sink; + + sink.WriteVarint32(kValue1); + + const uint8* sink_buffer = sink.Buffer(); + size_t length = sink.Length(); + + courgette::SourceStream source; + source.Init(sink_buffer, length); + + unsigned int value; + bool can_read = source.ReadVarint32(&value); + EXPECT_EQ(true, can_read); + EXPECT_EQ(kValue1, value); + EXPECT_EQ(0, source.Remaining()); +} + +TEST(StreamsTest, SimpleWriteRead2) { + courgette::SinkStream sink; + + sink.Write("Hello", 5); + + const uint8* sink_buffer = sink.Buffer(); + size_t sink_length = sink.Length(); + + courgette::SourceStream source; + source.Init(sink_buffer, sink_length); + + char text[10] = {0}; + bool can_read = source.Read(text, 5); + EXPECT_EQ(true, can_read); + EXPECT_EQ(0, memcmp("Hello", text, 5)); + EXPECT_EQ(0, source.Remaining()); +} + +TEST(StreamsTest, StreamSetWriteRead) { + courgette::SinkStreamSet out; + out.Init(4); + + const unsigned int kValue1 = 12345; + + out.stream(3)->WriteVarint32(kValue1); + + courgette::SinkStream collected; + + out.CopyTo(&collected); + + const uint8* collected_buffer = collected.Buffer(); + size_t collected_length = collected.Length(); + + courgette::SourceStreamSet in; + bool can_init = in.Init(collected_buffer, collected_length); + EXPECT_EQ(true, can_init); + + uint32 value; + bool can_read = in.stream(3)->ReadVarint32(&value); + EXPECT_EQ(true, can_read); + EXPECT_EQ(kValue1, value); + EXPECT_EQ(0, in.stream(3)->Remaining()); + EXPECT_EQ(0, in.stream(2)->Remaining()); +} + +TEST(StreamsTest, StreamSetWriteRead2) { + const size_t kNumberOfStreams = 4; + const unsigned int kEnd = ~0U; + + courgette::SinkStreamSet out; + out.Init(kNumberOfStreams); + + static const unsigned int data[] = { + 3, 123, 3, 1000, 0, 100, 2, 100, 0, 999999, + 0, 0, 0, 0, 1, 2, 1, 3, 1, 5, 0, 66, + // varint32 edge case values: + 1, 127, 1, 128, 1, 129, 1, 16383, 1, 16384, + kEnd + }; + + for (size_t i = 0; data[i] != kEnd; i += 2) { + size_t id = data[i]; + size_t datum = data[i + 1]; + out.stream(id)->WriteVarint32(datum); + } + + courgette::SinkStream collected; + + out.CopyTo(&collected); + + courgette::SourceStreamSet in; + bool can_init = in.Init(collected.Buffer(), collected.Length()); + EXPECT_EQ(true, can_init); + + for (size_t i = 0; data[i] != kEnd; i += 2) { + size_t id = data[i]; + size_t datum = data[i + 1]; + uint32 value = 77; + bool can_read = in.stream(id)->ReadVarint32(&value); + EXPECT_EQ(true, can_read); + EXPECT_EQ(datum, value); + } + + for (size_t i = 0; i < kNumberOfStreams; ++i) { + EXPECT_EQ(0, in.stream(i)->Remaining()); + } +} + +TEST(StreamsTest, SignedVarint32) { + courgette::SinkStream out; + + static const int32 data[] = { + 0, 64, 128, 8192, 16384, + 1 << 20, 1 << 21, 1 << 22, + 1 << 27, 1 << 28, + 0x7fffffff, -0x7fffffff + }; + + std::vector<int32> values; + for (size_t i = 0; i < sizeof(data)/sizeof(data[0]); ++i) { + int32 basis = data[i]; + for (int delta = -4; delta <= 4; ++delta) { + out.WriteVarint32Signed(basis + delta); + values.push_back(basis + delta); + out.WriteVarint32Signed(-basis + delta); + values.push_back(-basis + delta); + } + } + + courgette::SourceStream in; + in.Init(out); + + for (size_t i = 0; i < values.size(); ++i) { + int written_value = values[i]; + int32 datum; + bool can_read = in.ReadVarint32Signed(&datum); + EXPECT_EQ(written_value, datum); + } + + EXPECT_EQ(true, in.Empty()); +} + +TEST(StreamsTest, StreamSetReadWrite) { + courgette::SinkStreamSet out; + + { // Local scope for temporary stream sets. + courgette::SinkStreamSet subset1; + subset1.stream(3)->WriteVarint32(30000); + subset1.stream(5)->WriteVarint32(50000); + out.WriteSet(&subset1); + + courgette::SinkStreamSet subset2; + subset2.stream(2)->WriteVarint32(20000); + subset2.stream(6)->WriteVarint32(60000); + out.WriteSet(&subset2); + } + + courgette::SinkStream collected; + out.CopyTo(&collected); + courgette::SourceStreamSet in; + bool can_init_in = in.Init(collected.Buffer(), collected.Length()); + EXPECT_EQ(true, can_init_in); + + courgette::SourceStreamSet subset1; + bool can_read_1 = in.ReadSet(&subset1); + EXPECT_EQ(true, can_read_1); + EXPECT_EQ(false, in.Empty()); + + courgette::SourceStreamSet subset2; + bool can_read_2 = in.ReadSet(&subset2); + EXPECT_EQ(true, can_read_2); + EXPECT_EQ(true, in.Empty()); + + courgette::SourceStreamSet subset3; + bool can_read_3 = in.ReadSet(&subset3); + EXPECT_EQ(false, can_read_3); + + EXPECT_EQ(false, subset1.Empty()); + EXPECT_EQ(false, subset1.Empty()); + + uint32 datum; + EXPECT_EQ(true, subset1.stream(3)->ReadVarint32(&datum)); + EXPECT_EQ(30000, datum); + EXPECT_EQ(true, subset1.stream(5)->ReadVarint32(&datum)); + EXPECT_EQ(50000, datum); + EXPECT_EQ(true, subset1.Empty()); + + EXPECT_EQ(true, subset2.stream(2)->ReadVarint32(&datum)); + EXPECT_EQ(20000, datum); + EXPECT_EQ(true, subset2.stream(6)->ReadVarint32(&datum)); + EXPECT_EQ(60000, datum); + EXPECT_EQ(true, subset2.Empty()); +} diff --git a/third_party/courgette/testdata/en-US.dll b/third_party/courgette/testdata/en-US.dll Binary files differnew file mode 100644 index 0000000..f1ad46c --- /dev/null +++ b/third_party/courgette/testdata/en-US.dll diff --git a/third_party/courgette/testdata/setup1.exe b/third_party/courgette/testdata/setup1.exe Binary files differnew file mode 100644 index 0000000..da072f5 --- /dev/null +++ b/third_party/courgette/testdata/setup1.exe diff --git a/third_party/courgette/testdata/setup2.exe b/third_party/courgette/testdata/setup2.exe Binary files differnew file mode 100644 index 0000000..577a47f --- /dev/null +++ b/third_party/courgette/testdata/setup2.exe diff --git a/third_party/courgette/win32_x86_generator.h b/third_party/courgette/win32_x86_generator.h new file mode 100644 index 0000000..8d3e683 --- /dev/null +++ b/third_party/courgette/win32_x86_generator.h @@ -0,0 +1,126 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// This is the transformation and adjustment for Windows X86 executables.
+
+#ifndef COURGETTE_WIN32_X86_GENERATOR_H_
+#define COURGETTE_WIN32_X86_GENERATOR_H_
+
+#include "base/scoped_ptr.h"
+
+#include "third_party/courgette/ensemble.h"
+
+namespace courgette {
+
+class CourgetteWin32X86PatchGenerator : public TransformationPatchGenerator {
+ public:
+ CourgetteWin32X86PatchGenerator(Element* old_element,
+ Element* new_element,
+ CourgetteWin32X86Patcher* patcher)
+ : TransformationPatchGenerator(old_element, new_element, patcher) {
+ }
+
+ CourgettePatchFile::TransformationMethodId Kind() {
+ return CourgettePatchFile::T_COURGETTE_WIN32_X86;
+ }
+
+ Status WriteInitialParameters(SinkStream* parameter_stream) {
+ parameter_stream->WriteVarint32(old_element_->offset_in_ensemble());
+ parameter_stream->WriteVarint32(old_element_->region().length());
+ return C_OK;
+ // TODO(sra): Initialize |patcher_| with these parameters.
+ }
+
+ Status PredictTransformParameters(SinkStreamSet* prediction) {
+ return TransformationPatchGenerator::PredictTransformParameters(prediction);
+ }
+
+ Status CorrectedTransformParameters(SinkStreamSet* parameters) {
+ // No code needed to write an 'empty' parameter set.
+ return C_OK;
+ }
+
+ // The format of a transformed_element is a serialized EncodedProgram. We
+ // first disassemble the original old and new Elements into AssemblyPrograms.
+ // Then we adjust the new AssemblyProgram to make it as much like the old one
+ // as possible, before converting the AssemblyPrograms to EncodedPrograms and
+ // serializing them.
+ Status Transform(SourceStreamSet* corrected_parameters,
+ SinkStreamSet* old_transformed_element,
+ SinkStreamSet* new_transformed_element) {
+ // Don't expect any corrected parameters.
+ if (!corrected_parameters->Empty())
+ return C_GENERAL_ERROR;
+
+ // Generate old version of program using |corrected_parameters|.
+ // TODO(sra): refactor to use same code from patcher_.
+ AssemblyProgram* old_program = NULL;
+ Status old_parse_status =
+ ParseWin32X86PE(old_element_->region().start(),
+ old_element_->region().length(),
+ &old_program);
+ if (old_parse_status != C_OK)
+ return old_parse_status;
+
+ AssemblyProgram* new_program = NULL;
+ Status new_parse_status =
+ ParseWin32X86PE(new_element_->region().start(),
+ new_element_->region().length(),
+ &new_program);
+ if (new_parse_status != C_OK) {
+ DeleteAssemblyProgram(old_program);
+ return new_parse_status;
+ }
+
+ EncodedProgram* old_encoded = NULL;
+ Status old_encode_status = Encode(old_program, &old_encoded);
+ if (old_encode_status != C_OK) {
+ DeleteAssemblyProgram(old_program);
+ return old_encode_status;
+ }
+
+ Status old_write_status =
+ WriteEncodedProgram(old_encoded, old_transformed_element);
+ DeleteEncodedProgram(old_encoded);
+ if (old_write_status != C_OK) {
+ DeleteAssemblyProgram(old_program);
+ return old_write_status;
+ }
+
+ Status adjust_status = Adjust(*old_program, new_program);
+ DeleteAssemblyProgram(old_program);
+ if (adjust_status != C_OK) {
+ DeleteAssemblyProgram(new_program);
+ return adjust_status;
+ }
+
+ EncodedProgram* new_encoded = NULL;
+ Status new_encode_status = Encode(new_program, &new_encoded);
+ DeleteAssemblyProgram(new_program);
+ if (new_encode_status != C_OK)
+ return new_encode_status;
+
+ Status new_write_status =
+ WriteEncodedProgram(new_encoded, new_transformed_element);
+ DeleteEncodedProgram(new_encoded);
+ if (new_write_status != C_OK)
+ return new_write_status;
+
+ return C_OK;
+ }
+
+ Status Reform(SourceStreamSet* transformed_element,
+ SinkStream* reformed_element) {
+ return TransformationPatchGenerator::Reform(transformed_element,
+ reformed_element);
+ }
+
+ private:
+ ~CourgetteWin32X86PatchGenerator() { }
+
+ DISALLOW_COPY_AND_ASSIGN(CourgetteWin32X86PatchGenerator);
+};
+
+} // namespace courgette
+#endif // COURGETTE_WIN32_X86_GENERATOR_H_
diff --git a/third_party/courgette/win32_x86_patcher.h b/third_party/courgette/win32_x86_patcher.h new file mode 100644 index 0000000..4febad4 --- /dev/null +++ b/third_party/courgette/win32_x86_patcher.h @@ -0,0 +1,95 @@ +// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// This is the transformation for Windows X86 executables.
+
+#ifndef COURGETTE_WIN32_X86_PATCHER_H_
+#define COURGETTE_WIN32_X86_PATCHER_H_
+
+#include "third_party/courgette/ensemble.h"
+
+namespace courgette {
+
+// CourgetteWin32X86Patcher is a TransformationPatcher for Windows 32-bit
+// executables.
+//
+class CourgetteWin32X86Patcher : public TransformationPatcher {
+ public:
+ explicit CourgetteWin32X86Patcher(const Region& region)
+ : ensemble_region_(region) {
+ }
+
+ Status Init(SourceStream* parameter_stream) {
+ if (!parameter_stream->ReadVarint32(&base_offset_))
+ return C_BAD_TRANSFORM;
+ if (!parameter_stream->ReadVarint32(&base_length_))
+ return C_BAD_TRANSFORM;
+
+ if (base_offset_ > ensemble_region_.length())
+ return C_BAD_TRANSFORM;
+ if (base_length_ > ensemble_region_.length() - base_offset_)
+ return C_BAD_TRANSFORM;
+
+ return C_OK;
+ }
+
+ Status PredictTransformParameters(SinkStreamSet* predicted_parameters) {
+ // No code needed to write an 'empty' predicted parameter set.
+ return C_OK;
+ }
+
+ Status Transform(SourceStreamSet* corrected_parameters,
+ SinkStreamSet* transformed_element) {
+ Status status;
+ if (!corrected_parameters->Empty())
+ return C_GENERAL_ERROR; // Don't expect any corrected parameters.
+
+ AssemblyProgram* program = NULL;
+ status = ParseWin32X86PE(ensemble_region_.start() + base_offset_,
+ base_length_,
+ &program);
+ if (status != C_OK)
+ return status;
+
+ EncodedProgram* encoded = NULL;
+ status = Encode(program, &encoded);
+ DeleteAssemblyProgram(program);
+ if (status != C_OK)
+ return status;
+
+ status = WriteEncodedProgram(encoded, transformed_element);
+ DeleteEncodedProgram(encoded);
+ if (status != C_OK)
+ return status;
+
+ return status;
+ }
+
+ Status Reform(SourceStreamSet* transformed_element,
+ SinkStream* reformed_element) {
+ Status status;
+ EncodedProgram* encoded_program = NULL;
+ status = ReadEncodedProgram(transformed_element, &encoded_program);
+ if (status != C_OK)
+ return status;
+
+ status = Assemble(encoded_program, reformed_element);
+ DeleteEncodedProgram(encoded_program);
+ if (status != C_OK)
+ return status;
+
+ return C_OK;
+ }
+
+ private:
+ Region ensemble_region_;
+
+ uint32 base_offset_;
+ uint32 base_length_;
+
+ DISALLOW_COPY_AND_ASSIGN(CourgetteWin32X86Patcher);
+};
+
+} // namespace
+#endif // COURGETTE_WIN32_X86_PATCHER_H_
|