use rustc_hash::FxHashMap;
use crate::{
coff::{
CoffFile,
constants::{
IMAGE_COMDAT_SELECT_ANY, IMAGE_COMDAT_SELECT_ASSOCIATIVE,
IMAGE_COMDAT_SELECT_EXACT_MATCH, IMAGE_COMDAT_SELECT_LARGEST,
IMAGE_COMDAT_SELECT_NODUPLICATES, IMAGE_COMDAT_SELECT_SAME_SIZE,
IMAGE_SCN_LNK_COMDAT,
},
structs::SymbolAux,
},
error::{Error, Result},
};
struct Group<'data> {
file: usize,
section: u32,
key: &'data [u8],
selection: u8,
size: u32,
parent: u32,
kept: bool,
}
pub struct ComdatPlan {
dropped: Vec<(usize, u32)>,
}
impl ComdatPlan {
pub fn new(inputs: &[CoffFile<'_>]) -> Result<Self> {
let mut groups = collect(inputs);
select(&mut groups, inputs)?;
drop_orphans(&mut groups);
let mut dropped: Vec<(usize, u32)> = groups
.iter()
.filter(|g| !g.kept)
.map(|g| (g.file, g.section))
.collect();
dropped.sort_unstable();
Ok(Self { dropped })
}
pub fn is_dropped(&self, file: usize, section: u32) -> bool {
self.dropped.binary_search(&(file, section)).is_ok()
}
}
fn collect<'data>(inputs: &[CoffFile<'data>]) -> Vec<Group<'data>> {
let mut out = Vec::new();
for (file, input) in inputs.iter().enumerate() {
let facts = section_facts(input);
for section in input.sections() {
if section.characteristics & IMAGE_SCN_LNK_COMDAT == 0 {
continue;
}
let at = usize::try_from(section.index).unwrap_or(0);
let Some(&(selection, parent, key)) = facts.get(at) else {
continue;
};
let Some(selection) = selection else {
continue;
};
out.push(Group {
file,
section: section.index,
key: key.unwrap_or(section.name),
selection,
size: section.virtual_size.max(section.size_of_raw_data),
parent,
kept: true,
});
}
}
out
}
type SectionFacts<'data> = (Option<u8>, u32, Option<&'data [u8]>);
fn section_facts<'data>(input: &CoffFile<'data>) -> Vec<SectionFacts<'data>> {
let count = usize::try_from(input.number_of_sections()).unwrap_or(0);
let mut out = vec![(None, 0u32, None); count + 1];
for sym in input.symbols().iter() {
let Ok(ord) = usize::try_from(sym.section_number) else {
continue;
};
let Some(slot) = out.get_mut(ord) else {
continue;
};
match sym.aux {
SymbolAux::Section(aux) => {
slot.0 = Some(aux.selection);
slot.1 = aux.number;
}
_ if sym.is_external() && slot.2.is_none() => {
slot.2 = Some(sym.name);
}
_ => {}
}
}
out
}
fn select(groups: &mut [Group<'_>], inputs: &[CoffFile<'_>]) -> Result<()> {
let mut winners: FxHashMap<&[u8], usize> = FxHashMap::default();
for i in 0..groups.len() {
if groups[i].selection == IMAGE_COMDAT_SELECT_ASSOCIATIVE {
continue;
}
let key = groups[i].key;
let Some(&first) = winners.get(key) else {
winners.insert(key, i);
continue;
};
let loser = resolve_pair(groups, inputs, first, i)?;
groups[loser].kept = false;
if loser == first {
winners.insert(key, i);
}
}
Ok(())
}
fn resolve_pair(
groups: &[Group<'_>],
inputs: &[CoffFile<'_>],
first: usize,
second: usize,
) -> Result<usize> {
let (a, b) = (&groups[first], &groups[second]);
let any_largest = |x: u8, y: u8| {
(x == IMAGE_COMDAT_SELECT_ANY && y == IMAGE_COMDAT_SELECT_LARGEST)
|| (x == IMAGE_COMDAT_SELECT_LARGEST
&& y == IMAGE_COMDAT_SELECT_ANY)
};
if any_largest(a.selection, b.selection) {
return Ok(if b.size > a.size { first } else { second });
}
if a.selection != b.selection {
return Err(Error::Format(
"conflicting COMDAT selection kinds for one group",
));
}
match a.selection {
IMAGE_COMDAT_SELECT_NODUPLICATES => {
Err(Error::Format("duplicate COMDAT declared NODUPLICATES"))
}
IMAGE_COMDAT_SELECT_SAME_SIZE if a.size != b.size => {
Err(Error::Format("COMDAT copies differ in size"))
}
IMAGE_COMDAT_SELECT_EXACT_MATCH if !same_bytes(inputs, a, b) => {
Err(Error::Format("COMDAT copies differ in content"))
}
IMAGE_COMDAT_SELECT_LARGEST if b.size > a.size => Ok(first),
_ => Ok(second),
}
}
fn same_bytes(inputs: &[CoffFile<'_>], a: &Group<'_>, b: &Group<'_>) -> bool {
let data = |g: &Group<'_>| {
inputs
.get(g.file)
.and_then(|f| f.section_at(g.section))
.map(|s| s.data)
};
match (data(a), data(b)) {
(Some(x), Some(y)) => x == y,
_ => false,
}
}
fn drop_orphans(groups: &mut [Group<'_>]) {
let at: FxHashMap<(usize, u32), usize> = groups
.iter()
.enumerate()
.map(|(i, g)| ((g.file, g.section), i))
.collect();
let assoc: Vec<usize> = groups
.iter()
.enumerate()
.filter(|(_, g)| g.selection == IMAGE_COMDAT_SELECT_ASSOCIATIVE)
.map(|(i, _)| i)
.collect();
for _ in 0..=assoc.len() {
let mut changed = false;
for &i in &assoc {
if !groups[i].kept {
continue;
}
let key = (groups[i].file, groups[i].parent);
let orphan = at.get(&key).is_some_and(|&p| !groups[p].kept);
if orphan {
groups[i].kept = false;
changed = true;
}
}
if !changed {
return;
}
}
}